Robust Implementation of 4-D Geometric Algorithm and Applications

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

The incremental algorithm for constructing 4-dimensional convex hull of points was re-designed into a numerically robust algorithm. In the new algorithm, all the decisions on the topological structure are done by exact arithmetic using about five-times longer expression of integers, and geometric degeneracy is avoided by the symbolic perturbation technique. Also the computation is accelerated by floating-point filter, in such a way that computation is first done in floating point arithmetic and is switched to the exact arithmetic only when the precision turns out to be insufficient, This algorithm was applied to robust implementations of algorithms for many 3-dimehsional geometric structures, including the Voronoi diagram, the Delaunay diagram, the Laguerre Delaunay diagram, farthest-point Delaunay diagram, intersections of half spaces. The resulting source codes were made open for public use in the supervisor's web page.The other 4-dimensional geometric structure considered in this research is the time-space structure. In particular, robust algorithms for simulating crystal growth was designed and implemented using finite-difference techniques. This algorithm was applied to the construction of collision-free paths for a robust moving among hostile enemy robots.