Computationl Geometry problems

[JasonJo]

Point location query:

(a) Show how to do point in polygon query using O(n) preprocessing time and the actual query in 0(logn) time for a convex polygon without having to resort to triangulation as the preprocessing and without having to use Kirkpatrick's DAG as the query.

the O(n) preprocessing time is the time needed to build a data structure that allows us to use O(logn) query time.

(b) what about for x-monotone polygons?

I figure for (a), since the polygon is convex, i can find the left and right extreme points and binary search q by the x coordinate to see if it's between the right and left most extreme polnt of the polygon. but then what? do i do n left tests? that doesn't take logn, the binary search by x is log n, but n left tests is 0(n). any ideas?

also, i don't know how to adapt the method for the x-monotone polygon, any help or hints is greatly appreciated



Given a set S of n points in the plane, find a method of constructing a data structure that allows you to answer quicly a query of the form: is there a point of S within distance r of point q = (qx,qy) the query is specified by 3 numbers: (r, qx, qy)

 

[NateTG]

You might try part (b) of the problem first, since convex polygons are a strict subset of x-monotone polygons.
Hint: What do you know about x-monotone polygons?

For the second part:
Is there a fast way to figure out which s in S is closest to q?

 

[JasonJo]

x-monotone polygons are? i don't quite see the hint, sorry, i just have been going blank on this problem for the last few days

so I'm assuming we build a Voronoi diagram of the s points, and we can answer the query "quickly" using the Voronoi diagram data structure? am i close?

thanks

 

[NateTG]

x-monotone polygons are? i don't quite see the hint, sorry, i just have been going blank on this problem for the last few days

Well, what definition of x-monotone polygon are you using?

so I'm assuming we build a Voronoi diagram of the s points, and we can answer the query "quickly" using the Voronoi diagram data structure? am i close?

So, what would you do with the Voronoi diagram?

 

[JasonJo]

i'm using the definition that a polygon is x-monotone if the boundary of P can be split into two polygonal chains A and B such that each chain is monotone with respect to L

with the Voronoi diagram? i don't know lol

 

[NateTG]

i'm using the definition that a polygon is x-monotone if the boundary of P can be split into two polygonal chains A and B such that each chain is monotone with respect to L

Ah, OK. I was thinking of it as:
'Vertical' lines intersect the polyon at most once.

with the Voronoi diagram? i don't know lol

Ok, let's try a different approach, what if |S|=1, that is, if there is only one point in S, can you get the answer quickly?

 

[0rthodontist]

In a., fix (over all queries) an interior point P of the polygon and fix some other point R, and let the query point be Q. What information can be gained from angle RPQ?

 

[JasonJo]

i solved the one about the convex and x-monotone polygons

however, i don't get the: Given a set S of n points in the plane, find a method of constructing a data structure that allows you to answer quicly a query of the form: is there a point of S within distance r of point q = (qx,qy) the query is specified by 3 numbers: (r, qx, qy) still.

my professor said it had something to do with: recall the discussion about VOronoi diagrams and the relationship
to point location methods (e.g., Kirkpatrick's)

any help?

 

[0rthodontist]

I have not had the course you are taking, but this may be helpful: if you have a way of quickly determining which region of a Voronoi diagram a given point is in, that would allow you to solve this problem.

 

[JasonJo]

Edit:

Ah I Finally Got It!

Thanks Guys!

 

[0rthodontist]

If there were any points within r of q, then the closest point to q would be one of those points.