Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 59-62 |
| Number of pages | 4 |
| Journal | Information Processing Letters |
| Volume | 33 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 10 Nov 1989 |
| Externally published | Yes |
Keywords
- Lower bounds
- stabbing
- transversal
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Fingerprint
Dive into the research topics of 'Lower bounds for line stabbing'. These topics are generated from the title and abstract of the publication. Together, they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver