Rectilinear convex hull of points in 3D and applications
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.
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}
}
EUVIMED