Computational geometry and convexity
Bernard Chazelle · 1980
The purpose of this dissertation is two-fold: To assert the power of convexity as a crucial factor of efficiency in computational geometry and to show how non-convex design can also benefit from this feature. Most of the recent results in computational geometry have relied on the attribute of convexity, and have failed to generalize to arbitrary designs. To remedy this flaw, one general approach consists of decomposing the objects into convex pieces, then applying the procedures to each part. We study the problem of finding minimal convex decompositions in two and three dimensions. Among our major results are an O(n + N('3)) dynamic-programming algorithm for producing minimal decompositions of non-convex polygons and an O(nN('3)) heuristics for decomposing three-dimensional polyhedra. The latter procedure is worst-case optimal in the number of convex parts (within a constant multiplicative factor). In both cases, n denotes the total number of vertices, while N refers to the number of edges which exhibit reflex angles. We further explore the problem of finding minimal decompositions in three dimensions and prove its effective decidability. We also establish an (OMEGA)(N('2)) lower bound on the number of convex parts, and use this result to analyze the performance of the above heuristics. The second purpose of this study is to show how convexity can be used for greater efficiency. We justify this claim by studying one of the most fundamental questions in computational geometry: 'Do two convex objects intersect?' Note that the problem does not call for an actual computation of the intersections, which allows the possibility of sub-linear algorithms. The restriction to a simple detection rather than a complete computation is common in many applications areas where efficiency is the main concern. We present a class of practical algorithms for detecting intersections of lines, planes, polygons, and polyhedra in two and three dimensions. Their run-times range from O(log n) for the planar cases to O(log('3)n) for detecting the intersection of two polyhedra, where n represents the total number of vertices involved.