Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations
- PDF / 988,617 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 181 Views
Efficient computation of minimum-area rectilinear convex hull under rotation and generalizations Carlos Alegría1 · David Orden2 · Carlos Seara3
· Jorge Urrutia4
Received: 17 June 2019 / Accepted: 27 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Let P be a set of n points in the plane. We compute the value of θ ∈ [0, 2π) for which the rectilinear convex hull of P, denoted by 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 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, . . . , 2k. Let i = π − αi and = min{i : i = 1, . . . , 2k}. We obtain: (1) Given a set O such that ≥ π2 , we provide an algorithm to compute the O-convex hull of P in optimal O(n log n) time and O(n) space; If n n < π2 , the time and space complexities are O( log n) and O( ) respectively. (2) Given a π set O such that ≥ 2 , we compute and maintain the boundary of the Oθ -convex hull of P n for θ ∈ [0, 2π) in O(kn log n) time and O(kn) space, or if < π2 , in O(k log n) time and n π O(k ) space. (3) Finally, given a set O such that ≥ 2 , we compute, in O(kn log n) time and O(kn) space, the angle θ ∈ [0, 2π) such that the Oθ -convex hull of P has minimum (or maximum) area over all θ ∈ [0, 2π). Keywords Rectilinear convex hull · Restricted orientation convex hull · Minimum area
1 Introduction Restricted-orientation convexity is a generalization of traditional convexity that stems from the notion of restricted-orientation geometry, where the geometric objects under study comply with restrictions related to a fixed set of orientations. Restricted-orientation geometry
Extended abstracts related to this work were presented at the XIV Spanish Meeting on Computational Geometry [2] and the 30th European Workshop on Computational Geometry (EuroCG) [4]. Carlos Alegría: Research supported in part by UNAM Project PAEP, and by MIUR Proj. “AHeAD” No. 20174LF3T8. David Orden: Research supported by Projects MTM2017-83750-P of the Spanish Ministry of Science (AEI/FEDER, UE), and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Carlos Seara: Research supported by Projects Gen. Cat. DGR 2017SGR1640, MINECO MTM2015-63791-R, and Project PID2019-104129GB-I00 of the Spanish Ministry of Science and Innovation. Jorge Urrutia: Research supported in part by SEP-CONACYT 80268, PAPPIIT IN102117 Programa de Apoyo a la Investigación e Innovación Tecnológica UNAM. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 734922. Extended author information available on the last page of the article
123
Journal of Global Optimization
started with the work of Güting [19] in the early 1980s as a generalization of the study of orthogonal polygons, whose edges are parallel to the coordinate axes. Under what i
Data Loading...
