descriptionPublicationkeyboard_double_arrow_right Article , Other literature type 04 May 2024 English Publisher:Springer Science and Business Media LLCJournal:Journal of Global Optimization, volume 90, pages 551-571 (issn: 0925-5001, eissn: 1573-2916,

Authors: Pablo Pérez-Lantero; Carlos Seara; Jorge Urrutia;

doi: 10.1007/s10898-024-01402-3 , 10.60692/wyetm-49b16 , 10.60692/1dpex-dh335

handle: 2117/409496

Rectilinear convex hull of points in 3D and applications

- Summary
- Subjects
- Metrics

Abstract

AbstractLet 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 .

Related Organizations

Universitat Polite`cnica de Catalunya
Spain
National Autonomous University of Mexico
Mexico
Universitat Polit?cnica de Catalunya
Spain
Universitat Politècnica de Catalunya
Spain
University of Santiago Chile
Chile

Keywords

Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria, Hull, Fitting in 3D, Marine engineering, Computational Mechanics, Computational Geometry, Geometry, Geometria discreta, Computing Methodologies, Shape Representation, Engineering, Informàtica, Connected Component Labeling Algorithms, FOS: Mathematics, Analysis of Three-Dimensional Shape Structures, Classificació AMS::52 Convex and discrete geometry::52C Discrete geometry, Classificació AMS::68 Computer science::68U Computing methodologies and applications, Discrete Geometry, Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria convexa i discreta, Discrete geometry, Rectilinear convex hull, Mesh Generation Algorithms, Geometria convexa, Computer Graphics and Computer-Aided Design, Regular polygon, Convex geometry, Rotation around the Z-axis, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències, Combinatorics, Computer Science, Physical Sciences, Point Set Surfaces, Convex hull, Computer Vision and Pattern Recognition, Classificació AMS::52 Convex and discrete geometry::52A General convexity, 3D Reconstruction, Mathematics

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average