Robust Implementation of 4-D Geometric Algorithm and Applications

将构造点的四维凸船体的增量算法重新设计为数值鲁棒算法。在新算法中，所有拓扑结构的判定都是通过精确的算术运算完成的，所用的整数表达式约为原来的5倍，并且通过符号扰动技术避免了几何退化。该算法还采用浮点滤波器加速计算，即先用浮点算法进行计算，当精度不够时再用精确算法进行计算。该算法已应用于许多三维几何结构的鲁棒算法实现，包括Voronoi图、Delaunay图、Laguerre Delaunay图、最远点Delaunay图，半空间的交点。结果的源代码在导师的网页上公开供公众使用。本研究中考虑的另一个四维几何结构是时空结构。特别是，强大的算法模拟晶体生长的设计和实施使用有限差分技术。将该算法应用于机器人在敌方机器人之间的鲁棒运动的无碰撞路径的构建。

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.