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

DOI10.1016/0304-3975(79)90055-0MaRDI QIDQ1260355zbMATH OpenOpenAlexFDO

Authors F. P. Preparata, David E. Muller

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

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

Cites work

• Convex hulls of finite sets of points in two and three dimensions
• Finding the intersection of two convex polyhedra
• scientific article; zbMATH DE number 1241849 (Why is no real title available?)
• scientific article; zbMATH DE number 3308846 (Why is no real title available?)

Cited in

(19)

• 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
• Voronoi diagrams from convex hulls
• 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
• Faster goal-oriented shortest path search for bulk and incremental detailed routing
• Computing the shortest watchtower of a polyhedral terrain in \(O(n\log n)\) time.
• The complexity of many cells in arrangements of planes and related problems
• The complexity of linear programming
• An optimal online algorithm for halfplane intersection
• Faster goal-oriented shortest path search for bulk and incremental detailed routing
• Guarding precise and imprecise polyhedral terrains with segments
• Online multivariate changepoint detection: leveraging links with computational geometry
• Mechanical parts orienting: the case of a polyhedron on a table
• On the existence of maximum likelihood estimators in a multinomial choice model under positivity constraints
• A dual approach to detect polyhedral intersections in arbitrary dimensions
• An optimal parallel algorithm for linear programming in the plane

This page was built for publication: Finding the intersection of n half-spaces in time O(n log n)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1260355)