Adaptive Point Location in Planar Convex Subdivisions
| Autor: | Siu-Wing Cheng, Man-Kit Lau |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Computer Science::Information Retrieval
Applied Mathematics Astrophysics::Instrumentation and Methods for Astrophysics 0211 other engineering and technologies Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Computational Mathematics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics 010201 computation theory & mathematics Computer Science::General Literature Geometry and Topology ComputingMilieux_MISCELLANEOUS 021101 geological & geomatics engineering |
| Zdroj: | International Journal of Computational Geometry & Applications. 27:3-12 |
| ISSN: | 1793-6357 0218-1959 |
| DOI: | 10.1142/s0218195917600019 |
| Popis: | We present a planar point location structure for a convex subdivision [Formula: see text]. Given a query sequence of length [Formula: see text], the total running time is [Formula: see text], where [Formula: see text] is the number of vertices in [Formula: see text] and [Formula: see text] is the minimum time required by any linear decision tree for answering planar point location queries in [Formula: see text] to process the same query sequence. The running time includes the preprocessing time. Therefore, for [Formula: see text], our running time is only worse than the best possible bound by [Formula: see text] per query, which is much smaller than the [Formula: see text] query time offered by a worst-case optimal planar point location structure. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|