## Abstract

We show that in the worst case, Ω(n^{ d} ) sidedness queries are required to determine whether a set of n points in ℝ^{ d} is affinely degenerate, i.e., whether it contains d+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n^{ d} ) "collapsible" simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n^{ d} ) lower bound on the number of sidedness queries required to determine the order type of a set of n points in ℝ^{ d} . Using similar techniques, we also show that Ω(n^{ d+1}) in-sphere queries are required to decide the existence of spherical degeneracies in a set of n points in ℝ^{ d} .

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

Pages (from-to) | 41-57 |

Number of pages | 17 |

Journal | Discrete & Computational Geometry |

Volume | 13 |

Issue number | 1 |

DOIs | |

State | Published - Dec 1995 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics