TY - JOUR
T1 - Deterministic Algorithms for 2-d Convex Programming and 3-d Online Linear Programming
AU - Chan, Timothy M.
N1 - Funding Information:
*A portion of this work was performed while the author was visiting the Center for Geometric Computing at Johns Hopkins University, and it was supported in part by the Army Research Office under Grant DAAH04-96-1-0013. A preliminary version of the paper appeared in ``Proc. 8th ACM—SIAM Sympos. Discrete Algorithms,'' pp. 464—472, 1997. ²E-mail: [email protected].
PY - 1998/4
Y1 - 1998/4
N2 - We present a deterministic algorithm for solving two-dimensional convex programs with a linear objective function. The algorithm requires O(k log k) primitive operations for k constraints; if a feasible point is given, the bound reduces to O(k log k/log log k). As a consequence, we can decide whether k convex n-gons in the plane have a common intersection in O(k log n min{log k, log log n}) worst-case time. Furthermore, we can solve the three-dimensional online programming problem in o(log3 n) worst-case time per operation.
AB - We present a deterministic algorithm for solving two-dimensional convex programs with a linear objective function. The algorithm requires O(k log k) primitive operations for k constraints; if a feasible point is given, the bound reduces to O(k log k/log log k). As a consequence, we can decide whether k convex n-gons in the plane have a common intersection in O(k log n min{log k, log log n}) worst-case time. Furthermore, we can solve the three-dimensional online programming problem in o(log3 n) worst-case time per operation.
UR - http://www.scopus.com/inward/record.url?scp=0012527128&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0012527128&partnerID=8YFLogxK
U2 - 10.1006/jagm.1997.0914
DO - 10.1006/jagm.1997.0914
M3 - Article
AN - SCOPUS:0012527128
SN - 0196-6774
VL - 27
SP - 147
EP - 166
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -