Talk:Point location

From Wikipedia, the free encyclopedia

Ok guys, can anyone answer this question. If I have a shape which is very irregular, has lots of curves and non-stright lines but is bounded (ie the 'start' and 'end' points meet) and a point, how can I compute whether that point is inside or outside that shape?

Why is sorting required? The cell can be found in O(n) even if the points are in arbitrary order, can't it?
Amnon 12:33, 8 February 2007 (UTC)

Hi everybody, i searched for the article describing the O(log^d-1 n) time with O(n) space point location solution for rectilinear subdivisions in vein. So if anybody knows who published the paper containing the description, shall please leave the author and the title. Thanks! :) 84.56.215.129 19:51, 28 April 2007 (UTC) M. Heinzmann

[edit] Lipton

Is Richard J. Lipton the Lipton mentioned on this article? John Vandenberg 11:07, 7 August 2007 (UTC)

Yes. I added the citation and wikilink. —David Eppstein 15:35, 7 August 2007 (UTC)