Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles

Carlos Alegría (), Justin Dallant (), Pablo Pérez-Lantero () and Carlos Seara ()
Additional contact information
Carlos Alegría: Università Roma Tre
Justin Dallant: Université libre de Bruxelles
Pablo Pérez-Lantero: Universidad de Santiago de Chile
Carlos Seara: Universitat Politècnica de Catalunya

Journal of Global Optimization, 2025, vol. 92, issue 1, No 10, 227-251

Abstract: Abstract We explore an extension to rectilinear convexity of the classic problem of computing the convex hull of a set of geometric objects. Namely, we solve the problem of computing the rectilinear convex hull with arbitrary orientation for a set of segments and circles. We describe efficient algorithms to compute and maintain the objects appearing on the boundary of the rectilinear convex hull of such sets, while we rotate the coordinate axes by an angle that goes from 0 to $$2\pi $$ 2 π . We first consider a set of n segments. If the segments are not necessarily disjoint, we describe an algorithm that runs in optimal $$\Theta (n\log n)$$ Θ ( n log n ) time and $$O(n\alpha (n))$$ O ( n α ( n ) ) space, where $$\alpha (n)$$ α ( n ) is the extremely slowly growing inverse of Ackermann’s function. If instead the segments form a simple polygonal chain, we describe an algorithm that improves the previous space complexity to $$\Theta (n)$$ Θ ( n ) . We then extend the techniques used in these algorithms to a set of n circles. The resulting algorithm runs in optimal $$\Theta (n\log n)$$ Θ ( n log n ) time and $$\Theta (n)$$ Θ ( n ) space.

Keywords: Rectilinear convex hull; Segments; Simple polygonal line; Circles; Theory of computation; Computational geometry (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-025-01482-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:92:y:2025:i:1:d:10.1007_s10898-025-01482-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-025-01482-9

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().