Capturing the Shape of a Point Set with a Line Segment
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929334503079936 |
|---|---|
| author | van Beusekom, Nathan van Kreveld, Marc van Mulken, Max Roeloffzen, Marcel Speckmann, Bettina Wulms, Jules |
| author_facet | van Beusekom, Nathan van Kreveld, Marc van Mulken, Max Roeloffzen, Marcel Speckmann, Bettina Wulms, Jules |
| contents | 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$ if it is within distance $r$ of each point $p \in 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^3 h)$ time. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in $P$ move. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12285 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | 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 Computational Geometry 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$ if it is within distance $r$ of each point $p \in 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^3 h)$ time. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in $P$ move. |
| title | Capturing the Shape of a Point Set with a Line Segment |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2402.12285 |