Stabbing circles for sets of segments in the plane
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F49777513%3A23520%2F16%3A43928722" target="_blank" >RIV/49777513:23520/16:43928722 - isvavai.cz</a>
Result on the web
<a href="http://link.springer.com/chapter/10.1007/978-3-662-49529-2_22" target="_blank" >http://link.springer.com/chapter/10.1007/978-3-662-49529-2_22</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-662-49529-2_22" target="_blank" >10.1007/978-3-662-49529-2_22</a>
Alternative languages
Result language
angličtina
Original language name
Stabbing circles for sets of segments in the plane
Original language description
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 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 log^2 n) time algorithm. We also observe that the stabbing circle problem for S can be solved in optimal O(n^2) time and space by reducing the problem to computing the stabbing planes for a set of segments in 3D.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/LO1506" target="_blank" >LO1506: Sustainability support of the centre NTIS - New Technologies for the Information Society</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Theoretical Informatics - LATIN 2016 - LNCS 9644
ISBN
978-3-662-49529-2
ISSN
0302-9743
e-ISSN
—
Number of pages
16
Pages from-to
290-305
Publisher name
Springer
Place of publication
Heidelberg
Event location
Ensenada
Event date
Apr 11, 2016
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—