Point location query:(adsbygoogle = window.adsbygoogle || []).push({});

(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)

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Computationl Geometry problems

**Physics Forums | Science Articles, Homework Help, Discussion**