All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

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