Constant Workspace Algorithms for Computing Relative Hulls in the Plane
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_ | 1866918149352325120 |
|---|---|
| author | Chhabra, Himanshu Inkulu, R. |
| author_facet | Chhabra, Himanshu Inkulu, R. |
| contents | Constant workspace algorithms use a constant number of words in addition to the read-only input to the algorithm. In this paper, we devise algorithms to efficiently compute relative hulls in the plane using a constant workspace. Specifically, we devise algorithms for the following three problems: (i) Given two simple polygons P and Q with P \subset Q, compute a simple polygon P' with a perimeter of minimum length such that P \subseteq P' \subseteq Q. (ii) Given two simple polygons P and Q such that Q does not intersect the relative interior of P but it does intersect the relative interior of the convex hull of P, compute a weakly simple polygon P' with a perimeter of minimum length such that P \subseteq P', the convex hull of P contains P', and P' does not intersect the relative interior of Q. (iii) Given a set S of points located in a simple polygon P, compute a weakly simple polygon P' with a perimeter of minimum length such that P' \subseteq P and P' contains all the points in S. To our knowledge, no prior work devised algorithms to compute relative hulls using a constant workspace, and this work is the first such attempt. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10043 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constant Workspace Algorithms for Computing Relative Hulls in the Plane Chhabra, Himanshu Inkulu, R. Computational Geometry Constant workspace algorithms use a constant number of words in addition to the read-only input to the algorithm. In this paper, we devise algorithms to efficiently compute relative hulls in the plane using a constant workspace. Specifically, we devise algorithms for the following three problems: (i) Given two simple polygons P and Q with P \subset Q, compute a simple polygon P' with a perimeter of minimum length such that P \subseteq P' \subseteq Q. (ii) Given two simple polygons P and Q such that Q does not intersect the relative interior of P but it does intersect the relative interior of the convex hull of P, compute a weakly simple polygon P' with a perimeter of minimum length such that P \subseteq P', the convex hull of P contains P', and P' does not intersect the relative interior of Q. (iii) Given a set S of points located in a simple polygon P, compute a weakly simple polygon P' with a perimeter of minimum length such that P' \subseteq P and P' contains all the points in S. To our knowledge, no prior work devised algorithms to compute relative hulls using a constant workspace, and this work is the first such attempt. |
| title | Constant Workspace Algorithms for Computing Relative Hulls in the Plane |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2411.10043 |