Skip to main navigation Skip to search Skip to main content

Lower bounds for line stabbing

  • McGill University
  • University of Montreal

Research output: Contribution to journal › Journal Article › peer-review

21 Citations (Scopus)

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 languageEnglish
Pages (from-to)59-62
Number of pages4
JournalInformation Processing Letters
Volume33
Issue number2
DOIs
Publication statusPublished - 10 Nov 1989
Externally publishedYes

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