Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2017
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912192402554880 |
|---|---|
| author | Alegría-Galicia, Carlos Orden, David Seara, Carlos Urrutia, Jorge |
| author_facet | Alegría-Galicia, Carlos Orden, David Seara, Carlos Urrutia, Jorge |
| contents | Let $P$ be a set of $n$ points in the plane. We compute the value of $θ\in [0,2π)$ for which the rectilinear convex hull of $P$, denoted by $\mathcal{RH}_θ(P)$, has minimum (or maximum) area in optimal $O(n\log n)$ time and $O(n)$ space, improving the previous $O(n^2)$ bound. Let $\mathcal{O}$ be a set of $k$ lines through the origin sorted by slope and let $α_i$ be the sizes of the $2k$ angles defined by pairs of two consecutive lines, $i=1, \ldots , 2k$. Let $Θ_{i}=π-α_i$ and $Θ=\min\{Θ_i \colon i=1,\ldots,2k\}$. We obtain: (1) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we provide an algorithm to compute the $\mathcal{O}$-convex hull of $P$ in optimal $O(n\log n)$ time and $O(n)$ space; If $Θ< \fracπ{2}$, the time and space complexities are $O(\frac{n}Θ\log n)$ and $O(\frac{n}Θ)$ respectively. (2) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute and maintain the boundary of the ${\mathcal{O}}_θ$-convex hull of $P$ for $θ\in [0,2π)$ in $O(kn\log n)$ time and $O(kn)$ space, or if $Θ< \fracπ{2}$, in $O(k\frac{n}Θ\log n)$ time and $O(k\frac{n}Θ)$ space. (3) Finally, given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute, in $O(kn\log n)$ time and $O(kn)$ space, the angle $θ\in [0,2π)$ such that the $\mathcal{O}_θ$-convex hull of $P$ has minimum (or maximum) area over all $θ\in [0,2π)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1710_10888 |
| institution | arXiv |
| publishDate | 2017 |
| record_format | arxiv |
| spellingShingle | Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations Alegría-Galicia, Carlos Orden, David Seara, Carlos Urrutia, Jorge Computational Geometry Combinatorics Let $P$ be a set of $n$ points in the plane. We compute the value of $θ\in [0,2π)$ for which the rectilinear convex hull of $P$, denoted by $\mathcal{RH}_θ(P)$, has minimum (or maximum) area in optimal $O(n\log n)$ time and $O(n)$ space, improving the previous $O(n^2)$ bound. Let $\mathcal{O}$ be a set of $k$ lines through the origin sorted by slope and let $α_i$ be the sizes of the $2k$ angles defined by pairs of two consecutive lines, $i=1, \ldots , 2k$. Let $Θ_{i}=π-α_i$ and $Θ=\min\{Θ_i \colon i=1,\ldots,2k\}$. We obtain: (1) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we provide an algorithm to compute the $\mathcal{O}$-convex hull of $P$ in optimal $O(n\log n)$ time and $O(n)$ space; If $Θ< \fracπ{2}$, the time and space complexities are $O(\frac{n}Θ\log n)$ and $O(\frac{n}Θ)$ respectively. (2) Given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute and maintain the boundary of the ${\mathcal{O}}_θ$-convex hull of $P$ for $θ\in [0,2π)$ in $O(kn\log n)$ time and $O(kn)$ space, or if $Θ< \fracπ{2}$, in $O(k\frac{n}Θ\log n)$ time and $O(k\frac{n}Θ)$ space. (3) Finally, given a set $\mathcal{O}$ such that $Θ\ge\fracπ{2}$, we compute, in $O(kn\log n)$ time and $O(kn)$ space, the angle $θ\in [0,2π)$ such that the $\mathcal{O}_θ$-convex hull of $P$ has minimum (or maximum) area over all $θ\in [0,2π)$. |
| title | Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/1710.10888 |