Practical Computational Geometry - Unifying Study on Robust Geometric Computation

点击翻译按钮获取中文摘要

The goal of this approach is to compare various robust algorithms for geometric computation and to offer general advantages and disadvantages of the algorithms to users who want to choose algorithms that are suitable to their own purpose. The algorithm we studied can be divided into three approaches. The first is a pixel-boxel approach, which includes Asano's optimization for digital images, Inui's process planning algorithms, Kimura's soft object representation. The second is the topological approach, which includes Ohsawa's space modeling, Higashi's topologically-constrained computation, Sugihara's topology-oriented algorithms. The third is the algebraic approach, which includes Imai's optimization algorithms based on Grobner basis, Hirukawa's silhouette algorithms, and Sugihara's generalized Minkowski operations.These methods were applied to off-set computation, digital halftoning, crystal Voronoi diagram, soft-object modeling, simulation of surgical operation, solid modeling, collision detection, geometric packing, parametric shape design, minimum-cost flow, robot motion planning, mesh smoothing, and Minkowski sums. According to these experiences, we recognized that (i) the first approach is simple and suitable for low-dimensional problems, but is difficult to apply to high-dimensional problems, (ii) the second approach can be used in any numerical precision, but requires individual insight to each geometric problem, and (iii) the third approach can be used to any-dimensional problems, but requires special computational environment.