Nesting of Touching Polygons
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_ | 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 |