| Title: |
Capturing the Shape of a Point Set with a Line Segment |
| Authors: |
van Beusekom, Nathan; van Kreveld, Marc; van Mulken, Max; Roeloffzen, Marcel; Speckmann, Bettina; Wulms, Jules; Dep Informatica; Sub Geometric Computing; Geometric Computing; Kralovic, Rastislav; Kucera, Antonin |
| Publication Year: |
2024 |
| Subject Terms: |
Rotating calipers; Shape descriptor; Stabbing; Software |
| Description: |
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 log3 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. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
1868-8969 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482302 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482302 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.4F78305D |
| Database: |
BASE |