Capturing the Shape of a Point Set with a Line Segment

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Downloads (Pure)

Samenvatting

Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group’s shape carries meaning as well. In this paper, we represent a group’s shape using a simple geometric object, a line segment. Specifically, given a radius r, we say a line segment is representative of a point set P of n points if it is within distance r of each point p ∈ P. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius r using the shortest line segment. We describe an algorithm to find the shortest representative segment in O(n log h + h log³h) time, where h is the size of the convex hull of P. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in P move.
Originele taal-2Engels
Titel49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
RedacteurenRastislav Královič, Antonin Kučera
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's26:1-26:18
Aantal pagina's18
ISBN van elektronische versie978-3-95977-335-5
DOI's
StatusGepubliceerd - 23 aug. 2024
Evenement49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 - Bratislava, Slovakije
Duur: 26 aug. 202430 aug. 2024

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
Volume306
ISSN van elektronische versie1868-8969

Congres

Congres49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024
Verkorte titelMFCS 2024
Land/RegioSlovakije
StadBratislava
Periode26/08/2430/08/24

Vingerafdruk

Duik in de onderzoeksthema's van 'Capturing the Shape of a Point Set with a Line Segment'. Samen vormen ze een unieke vingerafdruk.

Citeer dit