Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems

TLDR

The algorithms are applicable to a range of geometric and quadratic programming problems. The paper presents linear‑time algorithms for linear programming in \(\mathbb{R}^2\) and \(\mathbb{R}^3\), with a preliminary version available from the author. The authors develop linear‑time algorithms for linear programming in \(\mathbb{R}^2\) and \(\mathbb{R}^3\), and for locating weighted centers of trees and other location‑theoretic problems. The results deliver linear‑time solutions for tasks such as the smallest enclosing circle, linear separability, weighted tree center, and convex quadratic programming in three dimensions, disproving a conjecture, correcting a prior error, and extending to higher dimensions.

Abstract

Linear-time algorithms for linear programming in $R^2 $ and $R^3 $ are presented. The methods used are applicable for other graphic and geometric problems as well as quadratic programming. For example, a linear-time algorithm is given for the classical problem of finding the smallest circle enclosing n given points in the plane; this disproves a conjecture by Shamos and Hoey [Proc.16th IEEE Symposium on Foundations of Computer Science, 1975] that this problem requires $\Omega (n\log n)$ time. An immediate consequence of the main result is that the problem of linear separability is solvable in linear time. This corrects an error in Shamos and Hoey’s paper, namely, that their $ O (n\log n)$ algorithm for this problem in the plane was optimal. Also, a linear-time algorithm is given for the problem of finding the weighted center of a tree, and algorithms for other common location-theoretic problems are indicated. The results apply also to the problem of convex quadratic programming in three dimensions. The results have already been extended to higher dimensions, and we know that linear programming can be solved in linear time when the dimension is fixed. This will be reported elsewhere; a preliminary version is available from the author.