EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Rectilinear convex hull of points in 3D and applications

Pablo Pérez-Lantero, Carlos Seara, Jorge Urrutia

Journal of Global Optimization · 2024-10 · 90 (2) · 551-571

DOI: 10.1007/s10898-024-01402-3 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Global Optimization, online erschienen am 04.05.2024. Verfasst von Pablo Pérez-Lantero und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministerio de Universidades.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Let P be a set of n points in $$\mathbb {R}^3$$ 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)$$ O ( n log n ) time and O ( n ) space algorithm to compute RCH ( P ). We also obtain an efficient $$O(n\log ^2 n)$$ O ( n log 2 n ) time and $$O(n\log n)$$ 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$$ R 3 around the Z -axis. We study some combinatorial properties of the rectilinear convex hulls of point sets in $$\mathbb {R}^3$$ R 3 . Finally, as an application of the obtained results, we show an approximation algorithm to an optimization fitting problem in $$\mathbb {R}^3$$ R 3 .

Förderung

  • Ministerio de Universidades

Zitieren

APA

Pérez-Lantero, P., Seara, C., & Urrutia, J. (2024). Rectilinear convex hull of points in 3D and applications. Journal of Global Optimization, 90(2), 551-571. https://doi.org/10.1007/s10898-024-01402-3

Vancouver

Pérez-Lantero P, Seara C, Urrutia J. Rectilinear convex hull of points in 3D and applications. Journal of Global Optimization. 2024;90(2):551-571. doi:10.1007/s10898-024-01402-3

BibTeX
@article{PrezLantero2024,
  author = {Pérez-Lantero, Pablo and Seara, Carlos and Urrutia, Jorge},
  title = {Rectilinear convex hull of points in 3D and applications},
  journal = {Journal of Global Optimization},
  year = {2024},
  volume = {90},
  number = {2},
  pages = {551--571},
  doi = {10.1007/s10898-024-01402-3}
}
Kostenlos starten →