I don't think it's possible to "do a convex polygon" (or to do most anything) in O(log n) time. Simply to examine each point requires O(n) time.
You can do binary search in O(log n) time, but that assumes that the points are sorted. ----- Original Message ----- From: "R.E. Boss" <[email protected]> Date: Wednesday, April 21, 2010 9:36 Subject: Re: [Jprogramming] Polygon containment To: 'Programming forum' <[email protected]> > > Van: [email protected] [mailto:programming- > > [email protected]] Namens Henry Rich > > Onderwerp: Re: [Jprogramming] Polygon containment > > > > If you have a gazillion points in a single polygon, you should pay > > attention to Boyko's comment that you can do a convex polygon > in O(log > > n) time. > > > > I think the approach would be to recursively cut the polygon into > > sections (perhaps just 2 sections), and then test each section by > > testing a chord between the first and last vertices; if you're > on the > > good side of that chord, you need no further testing of that > section.> > > Henry Rich > > > > > For statements like that ("you can do a convex polygon in O(log > n) time") I > would like a proof or (at least) a reference. > > Apart from that, I rather see some actual performance figures, since > probably it will be not too hard to come up with a process that > is O(n), but > in all real cases (much) faster than an O(log n) process. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
