Computer Science – Computational Geometry
Scientific paper
2008-05-27
Computer Science
Computational Geometry
Scientific paper
We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence, to support geometric queries in optimal time. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using $\lg n + 2\sqrt{\lg n} + O(\lg^{1/4} n)$ point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location in O(H+1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that use O(n) words or O(n lg n) bits, while saving drastic amounts of space. We then generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in $O(\lg^2 n)$ time.
Bose Prosenjit
Chen Eric Y.
He Meng
Maheshwari Anil
Morin Pat
No associations
LandOfFree
Succinct Geometric Indexes Supporting Point Location Queries 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 Succinct Geometric Indexes Supporting Point Location Queries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Succinct Geometric Indexes Supporting Point Location Queries will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-273999