Solving related two- and three-dimensional linear programming problems in logarithmic time

DOI10.1016/0304-3975(87)90101-0MaRDI QIDQ1091934zbMATH OpenOpenAlexFDO

Authors Jorge Stolfi, Kenneth L. Clarkson, Leonidas Guibas

Publication date 1987

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

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

zbMATH Keywords

linear inequalitiesspherical subdivision

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Review text

Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O(n log n) and space O(n). This subdivision in turn allows us to compute the point in space satisfying all inequalities and maximizing any desired linear objective function in time O(log n).

Recommendations

• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• scientific article; zbMATH DE number 4131946
• Linear Programming with Two Variables Per Inequality in Poly-Log Time
• Solving tall dense linear programs in nearly linear time
• An O(n log n)-algorithm for solving a special class of linear programs
• Linear Programming in O([n3/ln n]L) Operations
• Solving linear programs in the current matrix multiplication time
• Solving Linear Programs in the Current Matrix Multiplication Time
• Efficient algorithms for solving rank two and rank three bilinear programming problems
• A logarithmic-time solution to the point location problem for parametric linear programming

Cites work

• Finding the intersection of n half-spaces in time O(n log n)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions

Cited in

(5)

• Collision detection algorithm of a continuous type using spherical extreme vertex diagrams
• An efficient algorithm for determining the extreme vertices of a moving 3D convex polyhedron with respect to a plane
• Dynamic Three-Dimensional Linear Programming
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Solving tall dense linear programs in nearly linear time

This page was built for publication: Solving related two- and three-dimensional linear programming problems in logarithmic time

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