HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3136
Title: A simple entropy-based algorithm for planar point location
Authors: Arya, Sunil
Malamatos, Theocharis
Mount, David M.
Keywords: Entropy
Point location
Expected-case-complexity
Polygonal subdivision
Randomized algorithms
Issue Date: 2004
Citation: HKUST Theoretical Computer Science Center research Report; HKUST-TCSC-2004-10
Abstract: Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distributuion is the dominant term in the lower bound on the average-case search time. In this paper, we show that a very simple modification of a well- known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.
URI: http://hdl.handle.net/1783.1/3136
Appears in Collections:CSE Technical Reports

Files in This Item:

File Description SizeFormat
simple.pdf1872KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.