TY - CONF
T1 - A simple entropy-based algorithm for planar point location
T2 - Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
Y1 - 2001
A1 - Arya,Sunil
A1 - Malamatos,Theocharis
A1 - Mount, Dave
AB - 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. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. This problem has been considered before, but existing data structures are all quite complicated. 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 &Ogr;(H) average time. We also present empirical evidence for the practical efficiency of this approach.
JA - Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms
T3 - SODA '01
PB - Society for Industrial and Applied Mathematics
CY - Philadelphia, PA, USA
SN - 0-89871-490-7
UR - http://dl.acm.org/citation.cfm?id=365411.365457
ER -