1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Computationl Geometry problems

  1. May 2, 2006 #1
    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)
     
  2. jcsd
  3. May 2, 2006 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  4. May 2, 2006 #3
    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
     
  5. May 2, 2006 #4

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

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

    So, what would you do with the Voronoi diagram?
     
  6. May 2, 2006 #5
    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 dont know lol
     
  7. May 2, 2006 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

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

    Ok, let's try a different approach, what if [itex]|S|=1[/itex], that is, if there is only one point in [itex]S[/itex], can you get the answer quickly?
     
  8. May 2, 2006 #7

    0rthodontist

    User Avatar
    Science Advisor

    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?
     
    Last edited: May 2, 2006
  9. May 2, 2006 #8
    i solved the one about the convex and x-monotone polygons

    however, i dont 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???
     
  10. May 2, 2006 #9

    0rthodontist

    User Avatar
    Science Advisor

    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.
     
  11. May 2, 2006 #10
    Edit:

    Ah I Finally Got It!

    Thanks Guys!!!
     
    Last edited: May 2, 2006
  12. May 2, 2006 #11

    0rthodontist

    User Avatar
    Science Advisor

    If there were any points within r of q, then the closest point to q would be one of those points.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Computationl Geometry problems
  1. Geometry problem (Replies: 1)

  2. Geometry problem (Replies: 1)

Loading...