A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

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 languageEnglish
Title of host publication40th International Symposium on Computational Geometry (SoCG 2024)
EditorsWolfgang Mulzer, Jeff M. Phillips
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages16:1-16:16
Number of pages16
ISBN (Electronic)978-3-95977-316-4
DOIs
Publication statusPublished - 6 Jun 2024
Event40th International Symposium on Computational Geometry - Eugenides Foundation, Athens, Greece
Duration: 11 Jun 202414 Jun 2024
Conference number: 40
https://socg24.athenarc.gr/socg.html

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume293
ISSN (Electronic)1868-8969

Conference

Conference40th International Symposium on Computational Geometry
Abbreviated titleSoCG 2024
Country/TerritoryGreece
CityAthens
Period11/06/2414/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.

FundersFunder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

    Keywords

    • Furthest-neighbor queries
    • coreset
    • geodesic distance
    • polygons

    Fingerprint

    Dive into the research topics of 'A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon'. Together they form a unique fingerprint.

    Cite this