Numerically robust divide-and-conquer algorithm for constructing Voronoi diagrams

The paper presents a method to make the divide-and-conquer algorithm for constructing Voronoi diagrams to be numerically stable. Because of recent improvement by Katajainen & Koppinen, the divide-and-conquer algorithm attained the lowest time complexity both in the worst-case sense and in the average-case sense. However, it was not stable because it did not count on numerical errors. The authors make this algorithm numerically stable in the sense that the algorithm will never fail however large errors may take place in the course of computation. The present basic idea is that they place higher priority on some topological conditions than on numerical values and thus avoid inconsistency. A computer program based on the new algorithm turned out to have as good features as expected both from a numerical stability point of view and from a time complexity point of view. [In Japanese.]