## 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(n^{6} log n).

Original language | English (US) |
---|---|

Title of host publication | Algorithms and Complexity - 3rd Italian Conference, CIAC 1997, Proceedings |

Editors | Giancarlo Bongiovanni, Daniel Pierre Bovet, Giuseppe Di Battista |

Publisher | Springer Verlag |

Pages | 86-99 |

Number of pages | 14 |

ISBN (Print) | 3540625925, 9783540625926 |

DOIs | |

State | Published - 1997 |

Externally published | Yes |

Event | 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 - Rome, Italy Duration: Mar 12 1997 → Mar 14 1997 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1203 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 3rd Italian Conference on Algorithms and Complexity, CIAC 1997 |
---|---|

Country/Territory | Italy |

City | Rome |

Period | 3/12/97 → 3/14/97 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Computer Science