References

1

Francis Avnaim, Jean-Daniel Boissonnat, Olivier Devillers, Franco P. Preparata, and Mariette Yvinec. Evaluating Signs of Determinants Using Single-Precision Arithmetic. To appear in Algorithmica, 1996.

2

Marshall Bern and David Eppstein. Mesh Generation and Optimal Triangulation. Computing in Euclidean Geometry (Ding-Zhu Du and Frank Hwang, editors), Lecture Notes Series on Computing, volume 1, pages 23-90. World Scientific, Singapore, 1992.

3

L. Paul Chew. Guaranteed-Quality Mesh Generation for Curved Surfaces. Proceedings of the Ninth Annual Symposium on Computational Geometry, pages 274-280. Association for Computing Machinery, May 1993.

4

Kenneth L. Clarkson. Safe and Effective Determinant Evaluation. 33rd Annual Symposium on Foundations of Computer Science, pages 387-395. IEEE Computer Society Press, October 1992.

5

Rex A. Dwyer. A Faster Divide-and-Conquer Algorithm for Constructing Delaunay Triangulations. Algorithmica 2(2):137-151, 1987.

6

Steven Fortune. A Sweepline Algorithm for Voronoï Diagrams. Algorithmica 2(2):153-174, 1987.

7

Steven Fortune. Voronoï Diagrams and Delaunay Triangulations. Computing in Euclidean Geometry (Ding-Zhu Du and Frank Hwang, editors), Lecture Notes Series on Computing, volume 1, pages 193-233. World Scientific, Singapore, 1992.

8

Steven Fortune and Christopher J. Van Wyk. Efficient Exact Arithmetic for Computational Geometry. Proceedings of the Ninth Annual Symposium on Computational Geometry, pages 163-172. Association for Computing Machinery, May 1993.

9

Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized Incremental Construction of Delaunay and Voronoï Diagrams. Algorithmica 7(4):381-413, 1992.

10

Leonidas J. Guibas and Jorge Stolfi. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoï Diagrams. ACM Transactions on Graphics 4(2):74-123, April 1985.

11

C. L. Lawson. Software for C¹ Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161-194. Academic Press, New York, 1977.

12

D. T. Lee and B. J. Schachter. Two Algorithms for Constructing a Delaunay Triangulation. International Journal of Computer and Information Sciences 9(3):219-242, 1980.

13

Scott A. Mitchell. Cardinality Bounds for Triangulations with Bounded Minimum Angle. Sixth Canadian Conference on Computational Geometry, 1994. PostScript (141k).

14

Ernst P. Mücke, Isaac Saias, and Binhai Zhu. Fast Randomized Point Location Without Preprocessing in Two- and Three-dimensional Delaunay Triangulations. Proceedings of the Twelfth Annual Symposium on Computational Geometry. Association for Computing Machinery, May 1996. Abstract (with BibTeX citation), PostScript.

15

Jim Ruppert. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation. Journal of Algorithms 18(3):548-585, May 1995. Abstract (with BibTeX citation), PostScript (1526k).

16

Jonathan Richard Shewchuk. Robust Adaptive Floating-Point Geometric Predicates. Proceedings of the Twelfth Annual Symposium on Computational Geometry. Association for Computing Machinery, May 1996. Abstract (with BibTeX citation), PostScript (310k, 10 pages).

17

Daniel Dominic Sleator and Robert Endre Tarjan. Self-Adjusting Binary Search Trees. Journal of the Association for Computing Machinery 32(3):652-686, July 1985.

18

Peter Su and Robert L. Scot Drysdale. A Comparison of Sequential Delaunay Triangulation Algorithms. Proceedings of the Eleventh Annual Symposium on Computational Geometry, pages 61-70. Association for Computing Machinery, June 1995. PostScript for journal version (328k).