Deterministic algorithms for 2-d convex programming and 3-d online linear programming

Timothy M. Chan

Deterministic algorithms for 2-d convex programming and 3-d online linear programming

Timothy M. Chan

Research output: Contribution to conference › Paper › peer-review

Abstract

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 linear programming problem in o(log³ n) worst-case time per operation.

Original language	English (US)
Pages	464-472
Number of pages	9
State	Published - 1997
Externally published	Yes
Event	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA Duration: Jan 5 1997 → Jan 7 1997

Other

Other	Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
City	New Orleans, LA, USA
Period	1/5/97 → 1/7/97

ASJC Scopus subject areas

Software
General Mathematics

Library availability

Discover UIUC Full Text

Cite this

@conference{168d6ff0798047dca344d096c5db4f4b,

title = "Deterministic algorithms for 2-d convex programming and 3-d online linear programming",

abstract = "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 linear programming problem in o(log3 n) worst-case time per operation.",

author = "Chan, \{Timothy M.\}",

note = "*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].; Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 05-01-1997 Through 07-01-1997",

year = "1997",

language = "English (US)",

pages = "464--472",

}

TY - CONF

T1 - Deterministic algorithms for 2-d convex programming and 3-d online linear programming

AU - Chan, Timothy M.

N1 - *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 - 1997

Y1 - 1997

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 linear 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 linear programming problem in o(log3 n) worst-case time per operation.

UR - https://www.scopus.com/pages/publications/0030733356

UR - https://www.scopus.com/pages/publications/0030733356#tab=citedBy

M3 - Paper

AN - SCOPUS:0030733356

SP - 464

EP - 472

T2 - Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 5 January 1997 through 7 January 1997

ER -

Deterministic algorithms for 2-d convex programming and 3-d online linear programming

Abstract

Other

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this