Local polyhedra and geometric graphs (Q1775780)

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\).