Bounding a Polygon by a Minimum Number of Vertices
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908519128629248 |
|---|---|
| author | Abrahamsen, Mikkel Stade, Jack Yan, Shuyi Zhang, Hanwen |
| author_facet | Abrahamsen, Mikkel Stade, Jack Yan, Shuyi Zhang, Hanwen |
| contents | Suppose that a polygon $P$ is given as an array containing the vertices in counterclockwise order. We analyze how many vertices (including the index of each of these vertices) we need to know before we can bound $P$, i.e., report a bounded region $R$ in the plane such that $P\subset R$. We show that there exists polygons where $4\log_2 n+O(1)$ vertices are enough, while $\log_3n-o(\log n)$ must always be known. We thus answer the question up to a constant factor. This can be seen as an analysis of the shortest possible certificate or the best-case running time of any algorithm solving a variety of problems involving polygons, where a bound must be known in order to answer correctly. This includes various packing problems such as deciding whether a polygon can be contained inside another polygon. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounding a Polygon by a Minimum Number of Vertices Abrahamsen, Mikkel Stade, Jack Yan, Shuyi Zhang, Hanwen Computational Geometry Suppose that a polygon $P$ is given as an array containing the vertices in counterclockwise order. We analyze how many vertices (including the index of each of these vertices) we need to know before we can bound $P$, i.e., report a bounded region $R$ in the plane such that $P\subset R$. We show that there exists polygons where $4\log_2 n+O(1)$ vertices are enough, while $\log_3n-o(\log n)$ must always be known. We thus answer the question up to a constant factor. This can be seen as an analysis of the shortest possible certificate or the best-case running time of any algorithm solving a variety of problems involving polygons, where a bound must be known in order to answer correctly. This includes various packing problems such as deciding whether a polygon can be contained inside another polygon. |
| title | Bounding a Polygon by a Minimum Number of Vertices |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2509.04211 |