Stabbing circles for sets of segments in the plane

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Stabbing circles for sets of segments in the plane

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Stabbing circles for sets of segments in the plane

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/LO1506" target="_blank" >LO1506: Podpora udržitelnosti centra NTIS - Nové technologie pro informační společnost</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Theoretical Informatics - LATIN 2016 - LNCS 9644

ISBN

978-3-662-49529-2

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

16

Strana od-do

290-305

Název nakladatele

Springer

Místo vydání

Heidelberg

Místo konání akce

Ensenada

Datum konání akce

11. 4. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—