Rectilinear Convex Hull of Points in 3D
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\
- PDF / 571,282 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 212 Views
2
3
Departamento de Matem´ atica y Ciencia de la Computaci´ on, USACH, Santiago, Chile [email protected] Departament de Matem` atiques, Universitat Polit`ecnica de Catalunya, Barcelona, Spain [email protected] Instituto de Matem´ aticas, Universidad Nacional Aut´ onoma de M´exico, Mexico City, Mexico [email protected]
Abstract. Let P be a set of n points in R3 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 log2 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 R3 around the z-axis. Finally we study some properties of the rectilinear convex hulls of point sets in R3 .
1
Introduction
Let P be a set of n points in the plane. An open quadrant in the plane is the intersection of two open half-planes whose supporting lines are parallel to the x and y-axes. An open quadrant is called P -free if it contains no points of P . The rectilinear convex hull of P is the set W (P ), RCH(P ) = R2 \ W (P )∈W
where W denotes the set of all P -free open quadrants; see Fig. 1, left. The rectilinear convex hull of point sets has been studied mostly in the plane; e.g., see Ottmann et al. [9], Alegr´ıa et al. [1], and Bae et al. [3]. An open θ-quadrant is the intersection of two open half-planes whose supporting lines are orthogonal, one of which when rotated clockwise by θ degrees becomes horizontal. P. Perez-Lantero—Partially supported by projects CONICYT FONDECYT/Regular 1160543 (Chile), DICYT 041933PL Vicerrector´ıa de Investigaci´ on, Desarrollo e Innovaci´ on USACH (Chile), and Programa Regional STICAMSUD 19-STIC-02. C. Seara—Research supported by projects MTM2015-63791-R MINECO/FEDER and Gen. Cat. DGR 2017SGR1640. J. Urrutia—Research supported by PAPIIT IN105221 Programa de Apoyo a la Investigaci´ on e Innovaci´ on Tecnol´ ogica, UNAM. c Springer Nature Switzerland AG 2020 Y. Kohayakawa and F. K. Miyazawa (Eds.): LATIN 2020, LNCS 12118, pp. 296–307, 2020. https://doi.org/10.1007/978-3-030-61792-9_24
Rectilinear Convex Hull of Points in 3D
297
We define the θ-rectilinear convex hull RCHθ (P ) of a point set P as the set W (P ), RCHθ (P ) = R2 \ W (P )∈Wθ
where Wθ denotes the set of all P -free open θ-quadrants. Note that RCHθ (P ) changes as θ changes. In fact, as θ changes from 0 to π 2 there are O(n) combinatorially different rectilinear convex hulls; see [1,3]. Figure 1 right shows an example of a θ-rectilinear convex hull which happens to be disconnected.
Fig. 1. Left: RCH(P ). Right: RCHπ/6 (P ) of the same point set.
An open octant in R3 is the intersection of the three half-spaces, one perpendicular to the x-axis, one perpendicular to the y-axis, and another one perpendicular to the z-axis. As for the planar case, an octant is called P -free if it contains no elements of P . The rectilinear convex hull of a set of points in R3 is defined as W (P ), RCH 3 (P ) = R3
Data Loading...
