Nesting of Touching Polygons
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909320442019840 |
|---|---|
| author | Seemann, Carsten R. Stadler, Peter F. Hellmuth, Marc |
| author_facet | Seemann, Carsten R. Stadler, Peter F. Hellmuth, Marc |
| contents | Polygons are cycles embedded into the plane; their vertices are associated with $x$- and $y$-coordinates and the edges are straight lines. Here, we consider a set of polygons with pairwise non-overlapping interior that may touch along their boundaries. Ideas of the sweep line algorithm by Bajaj and Dey for non-touching polygons are adapted to accommodate polygons that share boundary points. The algorithms established here achieves a running time of $\mathcal{O}(n+N\log N)$, where $n$ is the total number of vertices and $N<n$ is the total number of "maximal outstretched segments" of all polygons. It is asymptotically optimal if the number of maximal outstretched segments per polygon is bounded. In particular, this is the case for convex polygons. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13040 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nesting of Touching Polygons Seemann, Carsten R. Stadler, Peter F. Hellmuth, Marc Computational Geometry Discrete Mathematics 05C10 Polygons are cycles embedded into the plane; their vertices are associated with $x$- and $y$-coordinates and the edges are straight lines. Here, we consider a set of polygons with pairwise non-overlapping interior that may touch along their boundaries. Ideas of the sweep line algorithm by Bajaj and Dey for non-touching polygons are adapted to accommodate polygons that share boundary points. The algorithms established here achieves a running time of $\mathcal{O}(n+N\log N)$, where $n$ is the total number of vertices and $N<n$ is the total number of "maximal outstretched segments" of all polygons. It is asymptotically optimal if the number of maximal outstretched segments per polygon is bounded. In particular, this is the case for convex polygons. |
| title | Nesting of Touching Polygons |
| topic | Computational Geometry Discrete Mathematics 05C10 |
| url | https://arxiv.org/abs/2409.13040 |