Edge-skeletons in arrangements with applications
The paper gives a method for constructing general edge-skeletons in three-dimensional arrangements of planes. Here, an edge-skeleton is a connected subset of the edges in this arrangement. This problem is not interesting per se but it has a number of applications, such as constructing Voronoi diagrams and power diagrams of arbitrary order in the plane or constructing space cutting trees in three dimensions. Indeed, whenever a problem can be mapped to an arrangement problem for three-dimensional planes, the presented algorithm can be used to compute a solution. In Section 4 of the paper the author describes a technique that consistently treats all degenerate cases such as four planes through a common point, etc. This technique allows the author to ignore all special cases when he implements the main part of the algorithm - those cases are taken care of in the lowest level of the implementation, that is, the procedures that provide the primitive geometric operations. This technique is general enough to be of substantial help for the implementation of many other geometric algorithms.
- scientific article; zbMATH DE number 1424290
- Constructing Arrangements of Lines and Hyperplanes with Applications
- scientific article; zbMATH DE number 4032498
- Improved construction of vertical decompositions of three-dimensional arrangements
- Computing Voronoi skeletons of a 3-D polyhedron by space subdivision
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Convex hulls of finite sets of points in two and three dimensions
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Halfspace range search: An algorithmic application of k-sets
- scientific article; zbMATH DE number 3716802 (Why is no real title available?)
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3454467 (Why is no real title available?)
- scientific article; zbMATH DE number 3407703 (Why is no real title available?)
- On k-Nearest Neighbor Voronoi Diagrams in the Plane
- On the number of line separations of a finite set in the plane
- Partitioning with two lines in the plane
- Power Diagrams: Properties, Algorithms and Applications
- Simple Partitions of Space
- Space searching for intersecting objects
- Voronoi Diagram in the Laguerre Geometry and Its Applications
- Voronoi diagrams and arrangements
- Computing a ham-sandwich cut in two dimensions
- Restricted-oriented convex sets
- Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements
- Algorithms for ham-sandwich cuts
- Splitting a configuration in a simplex
- Voronoi diagrams over dynamic scenes
- Tetrahedrizing point sets in three dimensions
- Symbolic treatment of geometric degeneracies
- Selection and sorting in totally monotone arrays
- A Complete Implementation for Computing General Dimensional Convex Hulls
- Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections
- A new duality result concerning Voronoi diagrams
- Eight-partitioning points in 3D, and efficiently too
- Eight-partitioning points in 3D, and efficiently too
- Order-k Voronoi diagrams of sites with additive weights in the plane
- On levels in arrangements and Voronoi diagrams
- A geometric consistency theorem for a symbolic perturbation scheme
This page was built for publication: Edge-skeletons in arrangements with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1091825)
