The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
New Lower Bounds for Convex Hull Problems in Odd Dimensions
Jeff Erickson,
Pages. 1198-1214
Abstract
Contents 1. Introduction
2. Geometric preliminaries
2.1. Definitions
2.2. The weird moment curve
3. $lceil d/2rceil$SUM hardness
4. Lower bounds for convex hull problems
5. Other computational primitives
6. Our models vs. real convex hull algorithms
7. Related problems
7.1. Affine degeneracies
7.2. An alternate proof in two dimensions
7.3. Circular degeneracies
8. Conclusions and open problems
Key words computational geometry, convex polytopes, degeneracy, lower bounds, decision trees, adversary arguments
Mathmatical Subject Classification 68Q25, 68U05, 52B55, 52B05