Passer à la navigation principale Passer à la recherche Passer au contenu principal

Lower bounds for line stabbing

  • McGill University
  • University of Montreal

Résultats de recherche: Contribution à un journal › Article publié dans une revue, révisé par les pairs › Revue par des pairs

21 Citations (Scopus)

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 originaleAnglais
Pages (de - à)59-62
Nombre de pages4
RevueInformation Processing Letters
Volume33
Numéro de publication2
Les DOIs
ÉtatPublié - 10 nov. 1989
Modification externeOui

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