DOI

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.

Язык оригиналаанглийский
Название основной публикацииLATIN 2016
Подзаголовок основной публикацииTheoretical Informatics - 12th Latin American Symposium, Proceedings
РедакторыGonzalo Navarro, Evangelos Kranakis, Edgar Chávez
ИздательSpringer Nature
Страницы290-305
Число страниц16
ISBN (печатное издание)9783662495285
DOI
СостояниеОпубликовано - 1 янв 2016
Событие12th Latin American Symposium on Theoretical Informatics, LATIN 2016 - Ensenada, Мексика
Продолжительность: 11 апр 201615 апр 2016

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том9644
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция12th Latin American Symposium on Theoretical Informatics, LATIN 2016
Страна/TерриторияМексика
ГородEnsenada
Период11/04/1615/04/16

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 38614548