Stabbing circles for some sets of Delaunay segments
| Autor: | Claverol Aguas, Mercè, Khramtcova, Elena, Papadopoulou, Evanthia, Saumell, Maria, Seara Ojea, Carlos |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
Triangulació
Segments TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science::Computer Vision and Pattern Recognition Stabbing Geometry Computer Science::Computational Geometry Triangulation Matemàtiques i estadística::Geometria [Àrees temàtiques de la UPC] Geometria computacional MathematicsofComputing_DISCRETEMATHEMATICS Circles Delaunay |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Recercat. Dipósit de la Recerca de Catalunya instname |
| Popis: | Let S be a set of n segments in the plane such that, for every segment, its two endpoints are adjacent in the Delaunay triangulation of the set of endpoints of all segments in S. Our goal is to compute all the combinatorially different stabbing circles for S, and the ones with maximum and minimum radius. We exploit a recent result to solve this problem in O(n log n) in two particular cases: (i) all segments in S are parallel; (ii) all segments in S have the same length. We also show that the problem of computing the stabbing circle of minimum radius of a set of n parallel segments of equal length (not necessarily satisfying the Delaunay condition) has an Omega(n log n) lower bound. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|