Résumé
We present an Ω(n log n) fixed order algebraic decision tree lower bound for determining the existence of a line stabber for a family of n line segments in the plane. We give the same lower bound for determining the existence of a line stabber for n translates of a circle in the plane. In proving this lower bound, we show that this problem is equivalent to determining if the width of a set of points is less than or equal to w. Through this transformation we can reexamine an old example by Hadwiger, Debrunner and Klee (1964) of a family of k+1 translates where every k translates have a line transversal but the entire family has no line transversal.
| Langue originale | Anglais |
|---|---|
| Pages (de - à) | 59-62 |
| Nombre de pages | 4 |
| Revue | Information Processing Letters |
| Volume | 33 |
| Numéro de publication | 2 |
| Les DOIs | |
| État | Publié - 10 nov. 1989 |
| Modification externe | Oui |
Classification disciplinaire ASJC Scopus
- Informatique théorique
- Traitement du signal
- Systèmes d'information
- Applications de l'informatique
Empreinte digitale
Voici les principaux termes ou expressions associés à « Lower bounds for line stabbing ». Ces libellés thématiques sont générés à partir du titre et du résumé de la publication. Ensemble, ils forment une empreinte digitale unique.Citer cette ressource
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver