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

Mark de Berg; Leonidas Theocharous

doi:10.4230/LIPIcs.SoCG.2024.16

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

Mark de Berg
, Leonidas Theocharous

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

61 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 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	https://doi.org/10.4230/LIPIcs.SoCG.2024.16
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 (Print)	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	https://socg24.athenarc.gr/socg.html

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
Nederlandse Organisatie voor Wetenschappelijk Onderzoek

Keywords

Furthest-neighbor queries
coreset
geodesic distance
polygons

Access to Document

10.4230/LIPIcs.SoCG.2024.16

pdfFinal published version, 1.15 MBLicence: CC BY

Cite this

de Berg, M., & Theocharous, L. (2024). A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon. In W. Mulzer, & J. M. Phillips (Eds.), 40th International Symposium on Computational Geometry (SoCG 2024) (pp. 16:1-16:16). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 293). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2024.16

@inproceedings{731bf8d9a8a740708a3c2d06e379f6bb,

title = "A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon",

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.",

keywords = "Furthest-neighbor queries, coreset, geodesic distance, polygons",

author = "\{de Berg\}, Mark and Leonidas Theocharous",

year = "2024",

month = jun,

day = "6",

doi = "10.4230/LIPIcs.SoCG.2024.16",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "16:1--16:16",

editor = "Wolfgang Mulzer and Phillips, \{Jeff M.\}",

booktitle = "40th International Symposium on Computational Geometry (SoCG 2024)",

note = "40th International Symposium on Computational Geometry, SoCG 2024 ; Conference date: 11-06-2024 Through 14-06-2024",

url = "https://socg24.athenarc.gr/socg.html",

}

de Berg, M & Theocharous, L 2024, A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon. in W Mulzer & JM Phillips (eds), 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), vol. 293, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 16:1-16:16, 40th International Symposium on Computational Geometry, Athens, Greece, 11/06/24. https://doi.org/10.4230/LIPIcs.SoCG.2024.16

A Coreset for Approximate Furthest-Neighbor Queries in a Simple Polygon. / de Berg, Mark; Theocharous, Leonidas.
40th International Symposium on Computational Geometry (SoCG 2024). ed. / Wolfgang Mulzer; Jeff M. Phillips. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. p. 16:1-16:16 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 293).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - de Berg, Mark

AU - Theocharous, Leonidas

N1 - Conference code: 40

PY - 2024/6/6

Y1 - 2024/6/6

N2 - 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.

AB - 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.

KW - Furthest-neighbor queries

KW - coreset

KW - geodesic distance

KW - polygons

UR - https://www.scopus.com/pages/publications/85195506064

U2 - 10.4230/LIPIcs.SoCG.2024.16

DO - 10.4230/LIPIcs.SoCG.2024.16

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 16:1-16:16

BT - 40th International Symposium on Computational Geometry (SoCG 2024)

A2 - Mulzer, Wolfgang

A2 - Phillips, Jeff M.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 40th International Symposium on Computational Geometry

Y2 - 11 June 2024 through 14 June 2024

ER -

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

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this