Removing Degeneracy May Require a Large Dimension Increase

by Jiří Matoušek and Petr Škovroň

Theory of Computing, Volume 3(8), pp. 159-177, 2007

Bibliography with links to cited articles

[1]   N. Amenta: Helly theorems and generalized linear programming. Discrete and Computational Geometry, 12:241–261, 1994. [Springer:bx1262r145x60505].

[2]   N. Amenta: A short proof of an interesting Helly-type theorem. Discrete and Computational Geometry, 15:423–427, 1996. [Springer:1fdgptcx3qfd4vm4].

[3]   H. Björklund, S. Sandberg, and S. Vorobyov: A discrete subexponential algorithm for parity games. In Proc. 20th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’03), Lect. Notes Comput. Sci. 2607, pp. 663–674. Springer-Verlag, 2003. [Springer:wpjqa08u8db47c3g].

[4]   C. Burnikel, K. Mehlhorn, and S. Schirra: On degeneracy in geometric computations. In Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA’94), pp. 16–23. SIAM, 1994. [SODA:314464.314474].

[5]   T. Chan: An optimal randomized algorithm for maximum Tukey depth. In Proc. 15th ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 430–436. SIAM, 2004. [SODA:982792.982853].

[6]   B. Chazelle and J. Matoušek: On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21:579–597, 1996. [Elsevier:10.1006/jagm.1996.0060].

[7]   K. L. Clarkson: Las Vegas algorithms for linear and integer programming. Journal of the ACM, 42:488–499, 1995. [JACM:201019.201036].

[8]   H. Edelsbrunner and E. P. Mücke: Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics, 9(1):66–104, 1990. [ACM:77635.77639].

[9]   I. Emiris and J. Canny: A general approach to removing degeneracies. SIAM J. Computing, 24:650–664, 1995. [SICOMP:10.1137/S0097539792235918].

[10]   K. Fischer: Smallest enclosing balls of balls. PhD thesis, ETH Zürich, Nr. 16168, 2005. Available at

[11]   B. Gärtner, J. Matoušek, L. Rüst, and P. Škovroň: Violator spaces: Structure and algorithms. Discr. Appl. Math., 2007. In press. Also in arXiv cs.DM/0606087. Extended abstract in Proc. 14th Europ. Symp. Algorithms (ESA’06). [arXiv:cs.DM/0606087].

[12]   B. Gärtner and I. Schurr: Linear programming and unique sink orientations. In Proc. 17th Ann. Symp. on Discrete Algorithms (SODA’06), pp. 749–757. ACM Press, 2006. [SODA:1109557.1109639].

[13]   B. Gärtner and E. Welzl: Linear programming - randomization and abstract frameworks. In Proc. 13th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’96), pp. 669–687, London, UK, 1996. Springer-Verlag.

[14]   B. Gärtner and E. Welzl: A simple sampling lemma: Analysis and applications in geometric optimization. Discrete and Computational Geometry, 25(4):569–590, 2001. [Springer:9flx12lr0mghtcc4].

[15]   N. Halman: On the power of discrete and of lexicographic Helly-type theorems. In Proc. 46th FOCS, pp. 463–472. IEEE Comp. Soc. Press, 2004. [FOCS:10.1109/FOCS.2004.47].

[16]   J. Matoušek: On geometric optimization with few violated constraints. Discrete and Computational Geometry, 14:365–384, 1995. [Springer:r750741557886767].

[17]   J. Matoušek, M. Sharir, and E. Welzl: A subexponential bound for linear programming. Algorithmica, 16:498–516, 1996. [Algorithmica:r378224736133416].

[18]   I. Schurr: Unique sink orientations of cubes. PhD thesis, ETH Zürich, Nr. 15747, 2004. Nr. 15747. Available at

[19]   M. Sharir and E. Welzl: A combinatorial bound for linear programming and related problems. In Proc. 9th Symp. on Theoretical Aspects of Computer Science (STACS’92), volume 577 of Lecture Notes in Computer Science, pp. 569–579. Springer-Verlag, 1992.

[20]   P. Škovroň: Removing degeneracies in LP-type problems may need to increase dimension. In Jana Šafránková and Jiří Pavl˚u, editors, Proc. 15th Week of Doctoral Students (WDS), pp. I:196–207. Matfyzpress, Prague, 2006.

[21]   T. Szabó and E. Welzl: Unique sink orientations of cubes. In Proc. 42nd FOCS, pp. 547–555. IEEE Comp. Soc. Press, 2001. [FOCS:10.1109/SFCS.2001.959931].

[22]   C. K. Yap: A geometric consistency theorem for a symbolic perturbation scheme. Journal of Computer and System Sciences, 40(1):2–18, 1990. [JCSS:10.1016/0022-0000(90)90016-E].