著者

杉原 厚吉

出版者

一般社団法人日本応用数理学会

雑誌

応用数理 (ISSN:09172270)

巻号頁・発行日

vol.1, no.4, pp.280-299, 1991-12-16

被引用文献数

12

---

New approaches are presented to the problem of topological inconsistency caused by geometric algorithms implemented in finite-precision arithmetic. In geometric computation numerical errors often create inconsistency in topological structures and thus cause theoretically correct algorithms to fail. To overcome this problem two approaches are considered for the case of constructing the Voronoi diagram as an example. In the first approach, higher-precision arithmetic is used to construct a closed world in which topological structures are judged always precisely, and the symbolic perturbation technique is employed to avoid complicated branches of processing for degenerate cases. In the second approach, the highest priority is placed on the maintenance of topological consistency and numerical results are used as lower-priority information; the resultant algorithm is robust in the sense that inconsistency never arises and is correct in the sense that the output converges to the true solution as the precision becomes higher.