On removing non-degeneracy assumptions in computational geometry: (Extended abstract)

Francisco Gómez, Suneeta Ramaswami, Godfried Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Existing methods for removing degeneracies in computational geometry can be classified as either approximation or perturbation methods. These methods give the implementer two rather unsatisfactory choices: find an approximate solution to the original problem given, or find an exact solution to an approximation of the original problem. We address an alternative approach that has received little attention in the computational geometry literature. Often a typical computational geometry paper will make a non-degeneracy assumption that can in fact be removed (without perturbing the input) by a global rigid transformation of the input. In these situations, by applying suitable pre- and post- processing steps to an algorithm, we obtain the exact solution to the original problem using the algorithm that assumes a non-degenerate input, even when that input is in fact degenerate. We consider several non-degeneracy assumptions that are typically made in the literature, propose algorithms for performing the pre- and post- processing steps that remove these degeneracies, analyze their complexity and, for some of these problems, give lower bounds on their worst-case complexity. The assumptions considered here include: (1) no two points in the plane on a vertical line (2) no two points in space lie on a vertical line (3) no two points in space have the same x-coordinate (4) no three points in space lie on a vertical plane and (5) no two line segments lie on a vertical plane. We propose low-degree polynomial-time solutions for the decision, computation and optimization versions of all these problems. For the optimization version of problem (5) we give an O(n 4) time algorithm, reducing the previous best running time of O(n6 log n).

Original languageEnglish (US)
Title of host publicationAlgorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings
EditorsGiancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista
PublisherSpringer Verlag
Pages86-99
Number of pages14
ISBN (Print)3540625925, 9783540625926
DOIs
StatePublished - 1997
Event3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, Italy
Duration: Mar 12 1997Mar 14 1997

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1203
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Italian Conference on Algorithms and Complexity, CIAC 1997
CountryItaly
CityRome
Period3/12/973/14/97

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On removing non-degeneracy assumptions in computational geometry: (Extended abstract)'. Together they form a unique fingerprint.

  • Cite this

    Gómez, F., Ramaswami, S., & Toussaint, G. (1997). On removing non-degeneracy assumptions in computational geometry: (Extended abstract). In G. Bongiovanni, D. P. Bovet, & G. Di Battista (Eds.), Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings (pp. 86-99). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1203). Springer Verlag. https://doi.org/10.1007/3-540-62592-5_63