论文标题
3D中的直线凸壳
Rectilinear Convex Hull of Points in 3D
论文作者
论文摘要
令$ p $为$ \ m athbb {r}^3 $的一组$ n $点，让$ rch（p）$为$ p $的直流凸壳。在本文中，我们获得了一个最佳$ O（n \ log n）$ - 时间和$ o（n）$ - 空间算法来计算$ rch（p）$。我们还获得了一个高效的$ O（n \ log^2 n）$ - 时间和$ o（n \ log n）$ - 空间算法，以计算和维护$ p $的直流式壳体的顶点，因为we rowate $ \ \ \ m rathbb r^3 $ a of $ z $ axisis of $ z $ -axis。最后，我们研究了$ \ mathbb {r}^3 $中的直线凸壳的一些属性。
Let $P$ be a set of $n$ points in $\mathbb{R}^3$ in general position, and let $RCH(P)$ be the rectilinear convex hull of $P$. In this paper we obtain an optimal $O(n\log n)$-time and $O(n)$-space algorithm to compute $RCH(P)$. We also obtain an efficient $O(n\log^2 n)$-time and $O(n\log n)$-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of $P$ as we rotate $\mathbb R^3$ around the $z$-axis. Finally we study some properties of the rectilinear convex hulls of point sets in $\mathbb{R}^3$.
