Solving related two- and three-dimensional linear programming problems in logarithmic time
Leo J. Guibas, Jorge Stolfi, Kenneth L. Clarkson · Theoretical Computer Science · 1987
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 ).