EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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, Carlos Seara

Journal of Global Optimization · 2025-05 · 92 (1) · 227-251

DOI: 10.1007/s10898-025-01482-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Global Optimization, online erschienen am 26.03.2025. Verfasst von Carlos Alegría und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministerio de Ciencia, Innovación y Universidades, Agencia Nacional de Investigación y Desarrollo, Universitat Politècnica de Catalunya.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Förderung

  • Ministerio de Ciencia, Innovación y Universidades
  • Agencia Nacional de Investigación y Desarrollo
  • Universitat Politècnica de Catalunya

Zitieren

APA

Alegría, C., Dallant, J., Pérez-Lantero, P., & Seara, C. (2025). Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles. Journal of Global Optimization, 92(1), 227-251. https://doi.org/10.1007/s10898-025-01482-9

Vancouver

Alegría C, Dallant J, Pérez-Lantero P, Seara C. Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles. Journal of Global Optimization. 2025;92(1):227-251. doi:10.1007/s10898-025-01482-9

BibTeX
@article{Alegra2025,
  author = {Alegría, Carlos and Dallant, Justin and Pérez-Lantero, Pablo and Seara, Carlos},
  title = {Time-optimal computation of the rectilinear convex hull with arbitrary orientation of sets of segments and circles},
  journal = {Journal of Global Optimization},
  year = {2025},
  volume = {92},
  number = {1},
  pages = {227--251},
  doi = {10.1007/s10898-025-01482-9}
}
Kostenlos starten →