Standard

Stabbing Circles for Sets of Segments in the Plane. / Claverol, Mercè; Khramtcova, Elena; Papadopoulou, Evanthia; Saumell, Maria; Seara, Carlos.

в: Algorithmica, Том 80, № 3, 01.03.2018, стр. 849-884.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Claverol, M, Khramtcova, E, Papadopoulou, E, Saumell, M & Seara, C 2018, 'Stabbing Circles for Sets of Segments in the Plane', Algorithmica, Том. 80, № 3, стр. 849-884. https://doi.org/10.1007/s00453-017-0299-z

APA

Claverol, M., Khramtcova, E., Papadopoulou, E., Saumell, M., & Seara, C. (2018). Stabbing Circles for Sets of Segments in the Plane. Algorithmica, 80(3), 849-884. https://doi.org/10.1007/s00453-017-0299-z

Vancouver

Claverol M, Khramtcova E, Papadopoulou E, Saumell M, Seara C. Stabbing Circles for Sets of Segments in the Plane. Algorithmica. 2018 Март 1;80(3):849-884. https://doi.org/10.1007/s00453-017-0299-z

Author

Claverol, Mercè ; Khramtcova, Elena ; Papadopoulou, Evanthia ; Saumell, Maria ; Seara, Carlos. / Stabbing Circles for Sets of Segments in the Plane. в: Algorithmica. 2018 ; Том 80, № 3. стр. 849-884.

BibTeX

@article{25f091ee55a241f2ae7c36caa9484259,
title = "Stabbing Circles for Sets of Segments in the Plane",
abstract = "Stabbing a set S of n segments in the plane by a line is a well-known 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 two cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute a representation of 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(nlog 2n) time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal O(n2) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D. Finally we show that the problem of computing the stabbing circle of minimum radius for a set of n parallel segments of equal length has an Ω(nlog n) lower bound.",
keywords = "Cluster Voronoi diagrams, Farthest-color Voronoi diagram, Hausdorff Voronoi diagram, Stabbing circle, Stabbing line segments, Voronoi diagram",
author = "Merc{\`e} Claverol and Elena Khramtcova and Evanthia Papadopoulou and Maria Saumell and Carlos Seara",
year = "2018",
month = mar,
day = "1",
doi = "10.1007/s00453-017-0299-z",
language = "English",
volume = "80",
pages = "849--884",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer Nature",
number = "3",

}

RIS

TY - JOUR

T1 - Stabbing Circles for Sets of Segments in the Plane

AU - Claverol, Mercè

AU - Khramtcova, Elena

AU - Papadopoulou, Evanthia

AU - Saumell, Maria

AU - Seara, Carlos

PY - 2018/3/1

Y1 - 2018/3/1

N2 - Stabbing a set S of n segments in the plane by a line is a well-known 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 two cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute a representation of 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(nlog 2n) time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal O(n2) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D. Finally we show that the problem of computing the stabbing circle of minimum radius for a set of n parallel segments of equal length has an Ω(nlog n) lower bound.

AB - Stabbing a set S of n segments in the plane by a line is a well-known 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 two cluster Voronoi diagrams, in particular, the Hausdorff and the farthest-color Voronoi diagram. Based on these diagrams, we provide a method to compute a representation of 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(nlog 2n) time and O(n) space algorithm. We also observe that the stabbing circle problem for S can be solved in worst-case optimal O(n2) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D. Finally we show that the problem of computing the stabbing circle of minimum radius for a set of n parallel segments of equal length has an Ω(nlog n) lower bound.

KW - Cluster Voronoi diagrams

KW - Farthest-color Voronoi diagram

KW - Hausdorff Voronoi diagram

KW - Stabbing circle

KW - Stabbing line segments

KW - Voronoi diagram

UR - http://www.scopus.com/inward/record.url?scp=85015008267&partnerID=8YFLogxK

U2 - 10.1007/s00453-017-0299-z

DO - 10.1007/s00453-017-0299-z

M3 - Article

AN - SCOPUS:85015008267

VL - 80

SP - 849

EP - 884

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3

ER -

ID: 38613739