2026-07-24T06:45:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20582 2024-08-23T05:50:28Z ddc:004 open_access

Capturing the Shape of a Point Set with a Line Segment van Beusekom, Nathan van Kreveld, Marc van Mulken, Max Roeloffzen, Marcel Speckmann, Bettina Wulms, Jules Shape descriptor Stabbing Rotating calipers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathan van Beusekom and Marc van Kreveld and Max van Mulken and Marcel Roeloffzen and Bettina Speckmann and Jules Wulms 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.26 urn:nbn:de:0030-drops-205820 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.26 eng https://creativecommons.org/licenses/by/4.0/legalcode