Abstract
The following problem is discussed: given n points in the plane (the sites) and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the griven sites and then locating the query point inone of its regions. Two algorithms are given, one that constructs the Voronoi diagram in O(n log n) time, and another that inserts a new sit on O(n) time. Both are based on the use of the Voronoi dual, or Delaunay triangulation, and are simple enough to be of practical value. the simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is, embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror image. Furthermore, just two operators are sufficients for building and modifying arbitrary diagrams.
- 1 BAUMGART, B.G. A polyhedron representation for computer vision. In 1975 National Computer Conference. AFIPS Conference Proceedings, vol. 44. AFIPS Press, Arlington, Va., 1975, pp. 589- 596.Google Scholar
- 2 BOOTS, B.N. Delaunay triangles: An alternative approach to point pattern analysis. In Proc. Assoc. Am. Geogr. 6 (1974), 26-29 (as cited by {20}).Google Scholar
- 3 BRMD, I. C., HILLYARD, R. C., AND STROUD, I. A. Stepwise construction of polyhedra in geometric modeling. In Mathematical Methods in Computer Graphics and Design, K. W. Brodlie, Ed. Academic Press, London, 1980, pp. 123-141.Google Scholar
- 4 BROWN, K.Q. Voronoi diagrams from convex hulls. Inf. Proc. Lett. 9, 5 (1979), 223-228.Google Scholar
- 5 DAMPHOUSSE, P. Cartographie topologique--La classification des cartes cellulaires. Unpublished Rep., Univ. of Tours, France.Google Scholar
- 6 EVEN, S. Algorithmic Combinatorics. Macmillan, N.Y., 1973.Google Scholar
- 7 GREEN, P. J., AND SIBSON, R. Computing Dirichlet tesselation in the plane. Comput. J. 21, 2 (1977), 168-173.Google Scholar
- 8 HARARY, F. Graph Theory. Addision-Wesley, Reading, Mass., 1972, p. 105.Google Scholar
- 9 I~~ANAGA, S., AND KAWADA, Y. Encyclopedic Dictionary of Mathematics, 2nd. ed. MIT Press, Cambridge, Mass., 1968.Google Scholar
- 10 KIRKPATRICK, D. Efficient computation of continuous skeletons. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (San Juan, Puerto Rico, Oct. 1979), IEEE, New York, pp. 18-27.Google Scholar
- 11 KIRKPATRICK, D. Optimal search in planar subdivisions. Tech. Rep. 81-13, Dep. of Computer Science, Univ. of British Columbia, 1981. Google Scholar
- 12 KNUTH, D.E. The Art of Computer Programming, vol. I: Fundamental Algorithms, 2nd. ed. Addision-Wesley, Reading, Mass., 1975. Google Scholar
- 13 LEE, D.T. Proximity and reachability in the plane. Tech. Rep. R-831, Coordinated Science Lab., Univ. of Illinois, Urbana, I11., 1978.Google Scholar
- 14 LEE, D. W., AND SCHACHTER, B.J. Two algorithms for constructing the Delaunay triangulation. Int. J. Comput. Inf. Sci. 9, 3 (1980), 219-242.Google Scholar
- 15 MANTYLA, M. J., AND SULONEN, R. GWB: A solid modeler with Euler operators. IEEE Comput. Graphics Appl. 2, 5 (Sept. 1982), 17-31.Google Scholar
- 16 MULLER, D. E., AND PREPARATA, F. P. Finding the intersection of two convex polyhedra. Theor. Comput. Sci. 7 (1978), 217-236.Google Scholar
- 17 PREPARATA, F. P., AND HONG, S.J. Convex hulls of finite sets of points in two and three dimensions. Commun. ACM 20 (1977), 87-93. Google Scholar
- 18 SHAMOS, M. I. Computational geometry. Ph.D. Dissertation, Yale University, New Haven, Conn., 1977. Google Scholar
- 19 SHAMOS, M. I., AND HOEV, D. Closest-point problems. In Proceedings o{ the 16th Annual IEEE Symposium on Foundations of Computer Science (Berkeley, CaliL, Oct. 1975), IEEE, New York, pp. 151-162.Google Scholar
- 20 WkTSON, D.F. Computing the n-dimensional Delaunay tesselation with application to Voronoi polytopes. Comput ,I. 24, 2 (1981), 167-172.Google Scholar
Index Terms
Primitives for the manipulation of general subdivisions and the computation of Voronoi
Recommendations
Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams
STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computingWe discuss the following problem: given n points in the plane (the “sites”), and an arbitrary query point q, find the site that is closest to q. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the ...
Optimal Search in Planar Subdivisions
A planar subdivision is any partition of the plane into (possibly unbounded) polygonal regions. The subdivision search problem is the following: given a subdivision S with n line segments and a query point P, determine which region of S contains P . We ...
Quading triangular meshes with certain topological constraints
In computer graphics and geometric modeling, shapes are often represented by triangular meshes (also called 3D meshes or manifold triangulations). The quadrangulation of a triangular mesh has wide applications. In this paper, we present a novel method ...
Comments