@conference {15645,
	title = {Entropy-preserving cuttings and space-efficient planar point location},
	booktitle = {Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms},
	series = {SODA {\textquoteright}01},
	year = {2001},
	month = {2001///},
	pages = {256 - 261},
	publisher = {Society for Industrial and Applied Mathematics},
	organization = {Society for Industrial and Applied Mathematics},
	address = {Philadelphia, PA, USA},
	abstract = {Point location is the problem of preprocessing a planar polygonal subdivision S into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. Given the probabilities pz that the query point lies within each cell z ∈ S, a natural question is how to design such a structure so as to minimize the expected-case query time. The entropy H of the probability distribution is the dominant term in the lower bound on the expected-case search time. Clearly the number of edges n of the subdivision is a lower bound on the space required. There is no known approach that simultaneously achieves the goals of H + \&Ogr;(H) query time and \&Ogr;(n) space. In this paper we introduce entropy-preserving cuttings and show how to use them to achieve query time H + \&Ogr;(H), using only \&Ogr;(n log* n) space.},
	isbn = {0-89871-490-7},
	url = {http://dl.acm.org/citation.cfm?id=365411.365456},
	author = {Arya,Sunil and Malamatos,Theocharis and Mount, Dave}
}
