On 21 April 2010 19:35, R.E. Boss <[email protected]> wrote: > 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.
R. Hui wrote: > 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. The algorithm works within log n time because it is an instance of binary search, i.e. at each step it halves the search space. More, precisely, it does the following. Let the tested point be P. 0. Choose any vertex B as a base point. Consider the two rays, r1 and r2, from B through the neighbouring vertices. Check if P is between the rays (left of r1, right of r2). If it is not, then it is not in the polygon, and you are done. 1. Check if the area between the rays contains polygon vertices. If not, go to 4. 2. Split the area between the rays into two parts by building another ray, r, from B towards the vertex that is halfway from r1 to r2 (measured by the number of such vertices). 3. Check whether P is to the left or right of r, and set r2=:r or r1=:r, accordingly. Go to 1. 4. The only part of the polygon left between r1 and r2 is a triangle BR1R2, where R1 is a vertex on r1 and R2 is a vertex on r2. Check if P is within the triangle by checking whether PR1R2 is ccw. > 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. Which one is really faster depends on what ‘real cases’ are. And that is something that perhaps only Dan knows. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
