Better Lower Bounds on Detecting

Affine and Spherical Degeneracies

Jeff Erickson
Computer Science Department Duke University Durham, NC 27708-0129 USA jeffe@cs.duke.edu |
Raimund Seidel
Fachberiech Informatik Universität des Saarlandes D-66123 Saarbrücken, Germany seidel@cs.uni-sb.de |

Discrete & Computational Geometry 18:239-240, 1997.

PostScript and
PDF versions are also available.

The lower bounds in [1] are based on the following adversary argument. Initially, the adversary presents a nondegenerate set of points. If the algorithm does not do enough work, the adversary can modify its input, introducing a degeneracy that the algorithm cannot detect. To prove some of our lower bounds, we first construct an adversary input for a restricted problem, in which some degeneracies are ignored, and then argue that this point set can be perturbed into general position to obtain an adversary input for the unrestricted problem. This perturbation technique is based on an incorrect assumption, and the proofs that use it are invalid.Let

Pbe a collection ofD-variate real polynomials. Each polynomial inPnaturally induces an algebraic surface inand these surfaces define a cellular decomposition ofR^{D}. Specifically, two points inR^{D}are in the same cell if and only if the sign of every polynomial inR^{D}Pis the same at both points. A surfacesnicely boundsa cellCin this decomposition if there is a continuous path from some point inCto some point outsideCthat intersectsstransversely and is either completely contained in or completely disjoint from every other surface induced byP.The correctness of the perturbation technique is based on the following incorrect claim (found on page 48 of [1]):

LetA counterexample is given by a set of four surfaces inCbe an arbitrary cell, and letC'be one of the cells in its boundary. Then every surface that nicely boundsC'also nicely boundsC., defined by the polynomialsR^{3}x-yz,y-xz,z=1, andz+1. See the figure below. LetC'be the line segment joining the points (0,0,-1) and (0,0,1).C'is a cell in the decomposition defined by these polynomials, and it is nicely bounded by the planesz=1andz=-1. However, no other cell is nicely bounded by both planes. In fact, none of the 2-dimensional cells that containC'is nicely bounded byeitherplane.Because of this error, the following results have incorrect proofs in [1]: Lemma 3.1, Theorem 3.2, Theorem 3.3, Theorem 4.2, Corollary 4.3, Theorem 5.2, Theorem 5.3, Theorem 5.6, and Corollary 5.7. Correct (and much simpler) proofs of all but one of these results appear in [3]. The only theorem whose proof we cannot correct is Theorem 5.6. Proving an

Omega(nlower bound for arbitrary spherical degeneracies remains an open problem.^{d+1})A similar error appears in Section 5 of [2]. The proofs in that section are also invalid, although similar results are proven correctly in [3].

Acknowledgments.We would like thank one of the anonymous referees of the journal version of [2] for demanding a proof of the false claim.## References

[1] J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete Comput. Geom. 13:41-57, 1995.[2] J. Erickson. Lower bounds for linear satisfiability problems. Proc. 6th Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 388-395, 1995.

[3] J. Erickson. New lower bounds for convex hull problems in odd dimensions. Proc. 12th Ann. ACM Symp. on Computational Geometry, pp. 1-9, 1996.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999