Erratum to
Better Lower Bounds on Detecting
Affine and Spherical Degeneracies

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 P be a collection of D-variate real polynomials. Each polynomial in P naturally induces an algebraic surface in R^D and these surfaces define a cellular decomposition of R^D. Specifically, two points in R^D are in the same cell if and only if the sign of every polynomial in P is the same at both points. A surface s nicely bounds a cell C in this decomposition if there is a continuous path from some point in C to some point outside C that intersects s transversely and is either completely contained in or completely disjoint from every other surface induced by P.

The correctness of the perturbation technique is based on the following incorrect claim (found on page 48 of [1]):

Let C be an arbitrary cell, and let C' be one of the cells in its boundary. Then every surface that nicely bounds C' also nicely bounds C.

A counterexample is given by a set of four surfaces in R³, defined by the polynomials x-yz, y-xz, z=1, and z+1. See the figure below. Let C' 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 planes z=1 and z=-1. However, no other cell is nicely bounded by both planes. In fact, none of the 2-dimensional cells that contain C' is nicely bounded by either plane.

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(n^d+1) lower bound for arbitrary spherical degeneracies remains an open problem.

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