Abstract
Let 𝒫 be a simple polygon with m vertices and let P be a set of n points inside 𝒫. We prove that there exists, for any ε > 0, a set C ⊂ P of size O(1/ε²) such that the following holds: for any query point q inside the polygon 𝒫, the geodesic distance from q to its furthest neighbor in C is at least 1-ε times the geodesic distance to its further neighbor in P. Thus the set C can be used for answering ε-approximate furthest-neighbor queries with a data structure whose storage requirement is independent of the size of P. The coreset can be constructed in O(1/(ε) (nlog(1/ε) + (n+m)log(n+m))) time.
Original language | English |
---|---|
Title of host publication | 40th International Symposium on Computational Geometry (SoCG 2024) |
Editors | Wolfgang Mulzer, Jeff M. Phillips |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 16:1-16:16 |
Number of pages | 16 |
ISBN (Electronic) | 978-3-95977-316-4 |
DOIs | |
Publication status | Published - 6 Jun 2024 |
Event | 40th International Symposium on Computational Geometry - Eugenides Foundation, Athens, Greece Duration: 11 Jun 2024 → 14 Jun 2024 Conference number: 40 https://socg24.athenarc.gr/socg.html |
Publication series
Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|
Volume | 293 |
ISSN (Electronic) | 1868-8969 |
Conference
Conference | 40th International Symposium on Computational Geometry |
---|---|
Abbreviated title | SoCG 2024 |
Country/Territory | Greece |
City | Athens |
Period | 11/06/24 → 14/06/24 |
Internet address |
Funding
Mark de Berg: MdB is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003. Leonidas Theocharous: LT is supported by the Dutch Research Council (NWO) through Gravitation-grant NETWORKS-024.002.003.
Funders | Funder number |
---|---|
Nederlandse Organisatie voor Wetenschappelijk Onderzoek |
Keywords
- Furthest-neighbor queries
- coreset
- geodesic distance
- polygons