TY - GEN
T1 - Capturing the Shape of a Point Set with a Line Segment
AU - van Beusekom, Nathan
AU - van Kreveld, Marc
AU - van Mulken, Max J.M.
AU - Roeloffzen, Marcel J.M.
AU - Speckmann, Bettina
AU - Wulms, Jules J.H.M.
PY - 2024/8/23
Y1 - 2024/8/23
N2 - 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.
AB - 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.
KW - Rotating calipers
KW - Shape descriptor
KW - Stabbing
UR - http://www.scopus.com/inward/record.url?scp=85203331097&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.MFCS.2024.26
DO - 10.4230/LIPIcs.MFCS.2024.26
M3 - Conference contribution
T3 - Leibniz International Proceedings in Informatics (LIPIcs)
SP - 26:1-26:18
BT - 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
A2 - Královič, Rastislav
A2 - Kučera, Antonin
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024
Y2 - 26 August 2024 through 30 August 2024
ER -