Finding the intersection of n half-spaces in time O(n log n)

DOI10.1016/0304-3975(79)90055-0zbMath0412.51001OpenAlexW1987647724MaRDI QIDQ1260355

David E. Muller, Franco P. Preparata

Publication date: 1979

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(79)90055-0

zbMATH Keywords

finding intersection of half-spaces in time O(n log n)interior and vertices of polyhedron

Mathematics Subject Classification ID

Linear programming (90C05) Software, source code, etc. for problems pertaining to geometry (51-04) Euclidean analytic geometry (51N20)

Related Items

Solving related two- and three-dimensional linear programming problems in logarithmic time, Linear programming in \({\mathbb{R}}^ 3\) and the skeleton and largest incircle of a convex polygon, Finding the convex hull of a sorted point set in parallel, The shortest watchtower and related problems for polyhedral terrains, Faster goal-oriented shortest path search for bulk and incremental detailed routing, Voronoi diagrams from convex hulls, An optimal parallel algorithm for linear programming in the plane, Optimal parallel algorithms for point-set and polygon problems, A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane, Mechanical parts orienting: the case of a polyhedron on a table, The complexity of linear programming, Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time., An optimal online algorithm for halfplane intersection, The complexity of many cells in arrangements of planes and related problems, A dual approach to detect polyhedral intersections in arbitrary dimensions

Cites Work

• Finding the intersection of two convex polyhedra
• Convex hulls of finite sets of points in two and three dimensions
• Unnamed Item
• Unnamed Item