- 1.T. Asano, M. Ed~hlro, H. Imai and M. iri, 'Practical Use of Bucketing Techniques in Computational Geometry,' in Computational Geometry, G. T. Toussaint (editor), Elsevier-North Holland (1985).Google Scholar
- 2.J. L. Bentley, B. W. Weide and A. C. Yao, 'Optimal Expected-Time Algorithms for Closest Point Problemsf ACM Transactions on Mathematical So Rleare O (1980), 563-580. Google ScholarDigital Library
- 3.P. J. Green and ft. Sibson, 'Computin{~ 'Duichlet Tessellations in the Plane,~ The Computer Journal 21 (1978), 168-173.Google ScholarCross Ref
- 4.It. N Horspool, 'Constructing the Voronoi I)ia4~ram in the Plane," Technical Report SOCS-79.12, McGill University, Montreal, Canada (1979).Google Scholar
- 5.T. Ohya, M. Iri and K. Murota, 'A Fast Voronoi Diagram Algorithm with Quaternary Tree Bucketing,~ Information Processing Letters 18 (1984), 227-231. Google ScholarDigital Library
- 6.T. Ohya, M. Iri and K. Murota, "Improvements of the Incremental Method for the Voronoi Diagram with a Comparison of Various Algorithms,' Journal of the Operations Research Society of Japan 27 (1984), 306-337.Google Scholar
- 7.F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag (1985). Google ScholarDigital Library
- 8.M. I. Shamos, "Computational Geometry," Ph.D. Thesis, Department of Computer Science, Yale University (1978). Google ScholarDigital Library
- 9.K. Sugihara and M. Iri, "Construction of the Voronoi Diagram for over 105 Generators in Single Precision Arithmetic,' First Canadian Conference on Computational Geometry, Montreal, Canada (1989).Google Scholar
Index Terms
- Error free incremental construction of Voronoi diagrams in the plane
Recommendations
The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces
We study the combinatorial complexity of Voronoi diagram of point sites on a general triangulated 2-manifold surface, based on the geodesic metric. Given a triangulated 2-manifold T of n faces and a set of m point sites S={s"1,s"2,...,s"m}@?T, we prove ...
Voronoi diagrams on the sphere
Given a set of compact sites on a sphere, we show that their spherical Voronoi diagram can be computed by computing two planar Voronoi diagrams of suitably transformed sites in the plane. We also show that a planar furthest-site Voronoi diagram can ...
Comments