Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913929983164416 |
|---|---|
| author | Picarella, Gianmarco van Kreveld, Marc Staals, Frank de Vries, Sjoerd |
| author_facet | Picarella, Gianmarco van Kreveld, Marc Staals, Frank de Vries, Sjoerd |
| contents | We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set $P$. We show that this problem can be solved in $O(n^6k)$ time and $O(n^3k)$ space, where $n$ is the size of $P$ and $k$ is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in $O(n^3k)$ time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04933 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter Picarella, Gianmarco van Kreveld, Marc Staals, Frank de Vries, Sjoerd Computational Geometry F.2.2 We study the problem of computing a convex region with bounded area and diameter that contains the maximum number of points from a given point set $P$. We show that this problem can be solved in $O(n^6k)$ time and $O(n^3k)$ space, where $n$ is the size of $P$ and $k$ is the maximum number of points in the found region. We experimentally compare this new algorithm with an existing algorithm that does the same but without the diameter constraint, which runs in $O(n^3k)$ time. For the new algorithm, we use different diameters. We use both synthetic data and data from an application in cancer detection, which motivated our research. |
| title | Computing Largest Subsets of Points Whose Convex Hulls have Bounded Area and Diameter |
| topic | Computational Geometry F.2.2 |
| url | https://arxiv.org/abs/2507.04933 |