A static optimality transformation with applications to planar point location

DOI10.1145/1998196.1998200zbMATH Open1283.68136arXiv1104.5597OpenAlexW2170711082MaRDI QIDQ5404403FDOQ5404403

Publication date: 24 March 2014

Published in: Proceedings of the twenty-seventh annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: Over the last decade, there have been several data structures that, given a planar subdivision and a probability distribution over the plane, provide a way for answering point location queries that is fine-tuned for the distribution. All these methods suffer from the requirement that the query distribution must be known in advance. We present a new data structure for point location queries in planar triangulations. Our structure is asymptotically as fast as the optimal structures, but it requires no prior information about the queries. This is a 2D analogue of the jump from Knuth's optimum binary search trees (discovered in 1971) to the splay trees of Sleator and Tarjan in 1985. While the former need to know the query distribution, the latter are statically optimal. This means that we can adapt to the query sequence and achieve the same asymptotic performance as an optimum static structure, without needing any additional information.

Full work available at URL: https://arxiv.org/abs/1104.5597

Recommendations

zbMATH Keywords

point location

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Symbolic computation and algebraic computation (68W30) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (3)

This page was built for publication: A static optimality transformation with applications to planar point location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404403)