Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3136
A simple entropybased algorithm for planar point location
Authors  Arya, Sunil
Malamatos, Theocharis Mount, David M. 


Issue Date  2004  
Source  HKUST Theoretical Computer Science Center research Report; HKUSTTCSC200410,  
Summary  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 p<sub>z</sub> 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 averagecase 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 pointlocation queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
