Stabbing a set S of n segments in the plane by a line is a wellknown problem. In this paper we consider the variation where the stabbing object is a circle instead of a line.We show that the problem is tightly connected to cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute all the combinatorially different stabbing circles for S, and the stabbing circles with maximum and minimum radius. We give conditions under which our method is fast. These conditions are satisfied if the segments in S are parallel, resulting in a O(n log2 n) time algorithm. We also observe that the stabbing circle problem for S can be solved in optimal O(n2) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D.

Original languageEnglish
Title of host publicationLATIN 2016
Subtitle of host publicationTheoretical Informatics - 12th Latin American Symposium, Proceedings
EditorsGonzalo Navarro, Evangelos Kranakis, Edgar Chávez
PublisherSpringer Nature
Pages290-305
Number of pages16
ISBN (Print)9783662495285
DOIs
StatePublished - 1 Jan 2016
Event12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Mexico
Duration: 11 Apr 201615 Apr 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9644
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference12th Latin American Symposium on Theoretical Informatics, LATIN 2016
Country/TerritoryMexico
CityEnsenada
Period11/04/1615/04/16

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 38614548