Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams
| Autor: | Jack Snoeyink, Timothy M. Chan, Chee-Keng Yap |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Convex hull
Pitteway triangulation MathematicsofComputing_GENERAL Convex set Computer Science::Computational Geometry Theoretical Computer Science Bowyer–Watson algorithm Combinatorics Computational Theory and Mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Convex polytope Mathematics::Metric Geometry Discrete Mathematics and Combinatorics Output-sensitive algorithm Geometry and Topology Voronoi diagram Point set triangulation MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Discrete & Computational Geometry. 18:433-454 |
| ISSN: | 0179-5376 |
| Popis: | In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E 4 . Our algorithm runs in \(O((n+f)\log^2 f)\) time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal \(O(n \log f + f)\) time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E 3 and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm'' of Kirkpatrick and Seidel in E 2 and also leads to improved output-sensitive results on constructing convex hulls in E d for any even constant d > 4. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink