Adaptive Point Location in Planar Convex Subdivisions

被引：1

作者：

Cheng, Siu-Wing ^{[1
]}

Lau, Man-Kit ^{[1
]}

机构：

[1] HKUST, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China

来源：

ALGORITHMS AND COMPUTATION, ISAAC 2015 | 2015年 / 9472卷

关键词：

Point location; Convex subdivision; Adaptive data structure; SEARCH; ALGORITHM;

D O I：

10.1007/978-3-662-48971-0_2

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a planar point location structure for a convex subdivision S. Given a query sequence of length m, the total running time is O(OPT+ m log log n+ n), where n is the number of vertices in S and OPT is the minimum running time to process the same query sequence by any linear decision tree for answering planar point location queries in S. The running time includes the preprocessing time. Therefore, for m >= n, our running time is only worse than the best possible bound by O(log log n) per query, which is much smaller than the O(log n) query time offered by an worst-case optimal planar point location structure.

引用

页码：14 / 22

页数：9

共 27 条

[1] ADAMY U., 1998, P 9 ANN ACM SIAM S D, P609
[2] Instance-Optimal Geometric Algorithms
Afshani, Peyman
Barbay, Jeremy
Chan, Timothy M.
[J]. 2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, : 129 - 138
[3] [Anonymous], P 7 INT C AUT LANG P
[4] Aronov Boris, 2013, Algorithms and Data Structures. 13th International Symposium, WADS 2013. Proceedings. LNCS 8037, P49, DOI 10.1007/978-3-642-40104-6_5
[5] Arya S, 2000, ANN IEEE SYMP FOUND, P208, DOI 10.1109/SFCS.2000.892108
[6] Arya S, 2000, LECT NOTES COMPUT SC, V1851, P353
[7] A Simple Entropy-Based Algorithm for Planar Point Location
Arya, Sunil
Malamatos, Theocharis
Mount, David M.
[J]. ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (02)
[8] Optimal expected-case planar point location
Arya, Sunil
Malamatos, Theocharis
Mount, David M.
Wong, Ka Chun
[J]. SIAM JOURNAL ON COMPUTING, 2007, 37 (02) : 584 - 610
[9] Boissonnat J.D., 1998, Algorithmic geometry
[10] Bose P., 2010, ARXIV10021092V1CSCG

← 1 2 3 →