TY - GEN

T1 - A static optimality transformation with applications to planar point location

AU - John, Iacono

PY - 2011

Y1 - 2011

N2 - In the past ten years, there have been a number of data structures that, given a distribution of planar point location queries, produce a planar point location data structure that is tuned for the provided distribution. These structures all suffer from the requirement that the query distribution be provided in advance. For the problem of point location in a triangulation, a data structure is presented that performs asymptotically as well as these structures, but does not require the distribution to be provided in advance. This result is the 2-d analogue of the jump from the optimum binary search trees of Knuth in 1971 which required that the distribution be provided, to the splay trees of Sleator and Tarjan in 1985 where in the static optimality theorem it was proven that splay trees had the same asymptotic performance of optimum search trees without being provided the probability distribution.

AB - In the past ten years, there have been a number of data structures that, given a distribution of planar point location queries, produce a planar point location data structure that is tuned for the provided distribution. These structures all suffer from the requirement that the query distribution be provided in advance. For the problem of point location in a triangulation, a data structure is presented that performs asymptotically as well as these structures, but does not require the distribution to be provided in advance. This result is the 2-d analogue of the jump from the optimum binary search trees of Knuth in 1971 which required that the distribution be provided, to the splay trees of Sleator and Tarjan in 1985 where in the static optimality theorem it was proven that splay trees had the same asymptotic performance of optimum search trees without being provided the probability distribution.

KW - Algorithms

UR - http://www.scopus.com/inward/record.url?scp=79960193965&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960193965&partnerID=8YFLogxK

U2 - 10.1145/1998196.1998200

DO - 10.1145/1998196.1998200

M3 - Conference contribution

AN - SCOPUS:79960193965

SN - 9781450306829

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 21

EP - 26

BT - Proceedings of the 27th Annual Symposium on Computational Geometry, SCG'11

T2 - 27th Annual ACM Symposium on Computational Geometry, SCG'11

Y2 - 13 June 2011 through 15 June 2011

ER -