TY - JOUR
T1 - Entropy, triangulation, and point location in planar subdivisions
AU - Collette, Séxbastien
AU - Dujmović, Vida
AU - Iacono, John
AU - Langerman, Stefan
AU - Morin, Pat
PY - 2012/7
Y1 - 2012/7
N2 - A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is (Mathematical Equation Presented) + O( (Mathematical Equation Presented) 1/2 + 1) where (Mathematical Equation Presented)(G, D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in Gunder the query distribution D. The preprocessing algorithm runs in O(nlog n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.
AB - A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is (Mathematical Equation Presented) + O( (Mathematical Equation Presented) 1/2 + 1) where (Mathematical Equation Presented)(G, D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in Gunder the query distribution D. The preprocessing algorithm runs in O(nlog n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.
KW - Computational geometry
KW - Minimum-entropy triangulation
KW - Point location
UR - http://www.scopus.com/inward/record.url?scp=84864863491&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84864863491&partnerID=8YFLogxK
U2 - 10.1145/2229163.2229173
DO - 10.1145/2229163.2229173
M3 - Article
AN - SCOPUS:84864863491
SN - 1549-6325
VL - 8
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 3
M1 - 29
ER -