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

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

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

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

Cited in

(5)

• Linear algorithm to find the largest intriangles of a planar convex polygon
• 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
• 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)