Local polyhedra and geometric graphs
In view of input models, the author investigates (nonconvex) polyhedra in \(d\)-space whose edge graphs are considered as special geometric graphs. Namely, a geometric graph (i.e., a graph whose edges are straight line segments) is called local if the longest edge at any vertex \(v\) of it is only a constant factor longer than the distance from \(v\) to its nearest neighbouring vertices, and the longest and shortest edges differ in length by at most a polynomial factor. A polyhedron in \(d\)-space is said to be local if its boundary consists of simplices and all edges form a local geometric graph. The author shows that any Boolean combination of two local polyhedra, with \(n\) vertices each, can be computed in \(O(n\log n)\) time. Similarly, efficient algorithmical approaches to the Minkowski sum of local polyhedra (for \(d= 2\) and \(d= 3\)) are presented, for the case of two polygons having complexity \(O(n^3\log n)\), and for two local polyhedra in 3-space yielding \(O(n^4\log^2n)\). Also it is confirmed that any local polyhedron in \(d\)-space has a binary space partition tree of size \(O(n\log^{d-2}n)\) and depth \(O(\log n)\), being tight in the worst case for \(d\leq 3\), and tight up to a logarithmic factor if \(d> 3\).
- A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
- A new approach to rectangle intersections part I
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- Analysis of a bounding box heuristic for object intersection
- Applications of random sampling in computational geometry. II
- Box-trees for collision checking in industrial installations
- Collision detection for deforming necklaces
- Collision detection for deforming necklaces
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
- Counting and Reporting Intersections of d-Ranges
- Efficient binary space partitions for hidden-surface removal and solid modeling
- Efficient maintenance and self-collision testing for kinematic chains
- FAST SOFTWARE FOR BOX INTERSECTIONS
- Generating well-shaped Delaunay meshes in 3D
- scientific article; zbMATH DE number 1263247 (Why is no real title available?)
- scientific article; zbMATH DE number 1303549 (Why is no real title available?)
- scientific article; zbMATH DE number 1033560 (Why is no real title available?)
- scientific article; zbMATH DE number 797443 (Why is no real title available?)
- scientific article; zbMATH DE number 1445288 (Why is no real title available?)
- Lectures on Polytopes
- Linear size binary space partitions for uncluttered scenes
- Lower bounds for algebraic decision trees
- Models and motion planning
- New lower bounds for Hopcroft's problem
- Nice point sets can have nasty Delaunay triangulations
- On the difficulty of triangulating three-dimensional nonconvex polyhedra
- Optimal binary space partitions for orthogonal objects
- OVERLAYING SURFACE MESHES, PART I: ALGORITHMS
- Range Searching and Point Location among Fat Objects
- Range searching in low-density environments
- Ray shooting on triangles in 3-space
- The complexity of the free space for motion planning amidst fat obstacles
- Decompositions and boundary coverings of non-convex fat polyhedra
- Globally and locally convex polyhedra
- Sigma-local graphs
- Local geometry of the 𝑘-curve graph
- Connect the Dot: Computing Feed-Links with Minimum Dilation
- scientific article; zbMATH DE number 29204 (Why is no real title available?)
- Local Topological Parameters in a Tetrahedral Representation
- Local polyhedra and geometric graphs
- (1+)-ANN data structure for curves via subspaces of bounded doubling dimension
- On the number of facets of three-dimensional Dirichlet stereohedra. IV: Quarter cubic groups
- Local characterization of polyhedral spaces
- On realistic terrains
This page was built for publication: Local polyhedra and geometric graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1775780)
