Local polyhedra and geometric graphs
type: Item
instance of: scholarly article
title: Local polyhedra and geometric graphs
zbMATH Open document ID: 1068.51023
author: Jeff Erickson
published in: Computational Geometry
publication date: 2005-05-04T00:00:00Z
review text: 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\).
reviewed by: Horst Martini
Mathematics Subject Classification ID: 51M20
Mathematics Subject Classification ID: 52B55
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W99
zbMATH DE Number: 2164980
zbMATH Keywords: geometric graph
zbMATH Keywords: Minkowski sum
zbMATH Keywords: binary space partition
zbMATH Keywords: input model
zbMATH Keywords: bounding volume hierarchy
zbMATH Keywords: Boolean combination
zbMATH Keywords: intersection detection
describes a project that uses: Stanford 3D Scanning Repository
MaRDI profile type: Publication
full work available at URL: j.comgeo.2004.08.004
OpenAlex ID: W4210283320
cites work: Collision detection for deforming necklaces
cites work: Q4952601
cites work: Linear size binary space partitions for uncluttered scenes
cites work: Models and motion planning
cites work: Q4344150
cites work: Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
cites work: Algorithms for bichromatic line-segment problems and polyhedral terrains
cites work: Applications of random sampling in computational geometry. II
cites work: A new approach to rectangle intersections part I
cites work: New lower bounds for Hopcroft's problem
cites work: Nice point sets can have nasty Delaunay triangulations
cites work: Box-trees for collision checking in industrial installations
cites work: OVERLAYING SURFACE MESHES, PART I: ALGORITHMS
cites work: Generating well-shaped Delaunay meshes in 3D
cites work: Efficient maintenance and self-collision testing for Kinematic Chains
cites work: Q4234119
cites work: Q4848605
cites work: Range Searching and Point Location among Fat Objects
cites work: Efficient binary space partitions for hidden-surface removal and solid modeling
cites work: Optimal binary space partitions for orthogonal objects
cites work: Ray shooting on triangles in 3-space
cites work: A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation
cites work: On the difficulty of triangulating three-dimensional nonconvex polyhedra
cites work: Range searching in low-density environments
cites work: Counting and Reporting Intersections of d-Ranges
cites work: The complexity of the free space for motion planning amidst fat obstacles
cites work: Lower bounds for algebraic decision trees
cites work: Q4250173
cites work: Analysis of a bounding box heuristic for object intersection
cites work: Lectures on Polytopes
cites work: FAST SOFTWARE FOR BOX INTERSECTIONS
DOI: 10.1016/J.COMGEO.2004.08.004
description: scientific article; zbMATH DE number 2164980