Distance-Sensitive Planar Point Location

Abstract: Let

m a t h c a l S

be a connected planar polygonal subdivision with

n

edges that we want to preprocess for point-location queries, and where we are given the probability

g a m m a_{i}

that the query point lies in a polygon

P_{i}

of

m a t h c a l S

. We show how to preprocess

m a t h c a l S

such that the query time for a point~

p i n P_{i}

depends on~

g a m m a_{i}

and, in addition, on the distance from

p

to the boundary of~

P_{i}

---the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time

O l e f t (m i n l e f t (l o g n, 1 + l o g f r a c m a t h r m a r e a (P_{i}) g a m m a_{i} D e l t a_{p}^{2} i g h t) i g h t)

, where

D e l t a_{p}

is the shortest Euclidean distance of the query point~

p

to the boundary of

P_{i}

. Our structure uses

O (n)

space and

O (n l o g n)

preprocessing time. It is based on a decomposition of the regions of

m a t h c a l S

into convex quadrilaterals and triangles with the following property: for any point

p i n P_{i}

, the quadrilateral or triangle containing~

p

has area

O m e g a (D e l t a_{p}^{2})

. For the special case where

m a t h c a l S

is a subdivision of the unit square and

g a m m a_{i} = m a t h r m a r e a (P_{i})

, we present a simpler solution that achieves a query time of

O l e f t (m i n l e f t (l o g n, l o g f r a c 1 D e l t a_{p}^{2} i g h t) i g h t)

. The latter solution can be extended to convex subdivisions in three dimensions.

Recommendations

Cited in

(4)

This page was built for publication: Distance-Sensitive Planar Point Location