Point Location in Disconnected Planar Subdivisions

Details Point Location in Disconnected Planar Subdivisions Point Location in Disconnected Planar Subdivisions

2010-01-15

arxiv.org/abs/1001.2763v1

Computer Science

Computational Geometry

Scientific paper

Let $G$ be a (possibly disconnected) planar subdivision and let $D$ be a probability measure over $\R^2$. The current paper shows how to preprocess $(G,D)$ into an O(n) size data structure that can answer planar point location queries over $G$. The expected query time of this data structure, for a query point drawn according to $D$, is $O(H+1)$, where $H$ is a lower bound on the expected query time of any linear decision tree for point location in $G$. This extends the results of Collette et al (2008, 2009) from connected planar subdivisions to disconnected planar subdivisions. A version of this structure, when combined with existing results on succinct point location, provides a succinct distribution-sensitive point location structure.

Affiliated with

Also associated with

No associations

Rating

Point Location in Disconnected Planar Subdivisions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Point Location in Disconnected Planar Subdivisions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Point Location in Disconnected Planar Subdivisions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-88006