Voronoi diagrams with respect to criteria on vision information. (English) Zbl 1158.68046

Asano, Tetsuo; Katoh, Naoki; Tamaki, Hisao; Tokuyama, Takeshi

Japan J. Ind. Appl. Math. 25, No. 2, 149-164 (2008).

Summary: Voronoi diagrams for a set of geometric objects is a partition of the plane (or space in higher dimensions) into disjoint regions each dominated by some given object under a predetermined criterion. In this paper we are interested in various measures associated with criteria on goodness of an input line segment with respect to each point in the plane as the “point of view”. These measures basically show how well a segment or information displayed on the segment can be seen from the point. Mathematically, the measures are defined in terms of the shapes of the triangle determined by the point and the line segment. We study the combinatorial and algorithmic complexities of those Voronoi diagrams. We also study an associated optimization problem: find a point that maximizes the smallest measure value over the measures with respect to all the given line segments. We give sufficient conditions for an optimal point to lie on a Voronoi edge and present a heuristic optimization algorithm for those measures having this property.

MSC:

68U05

Computer graphics; computational geometry (digital and algorithmic aspects)

Keywords:

measure on triangles; optimization

Software:

Triangle

References:

[1]	P. Agarwal, O. Schwarzkopf and M. Sharir, The Overlay of Lower Envelopes and its Applications. Discrete & Computational Geometry,15 (1996), 1–13. · Zbl 0840.68115
[2]	T. Asano, Aspect-ratio Voronoi Diagram with Applications. Proc. International Symposium on Voronoi Diagram in Science and Engineering, Banff, Canada, 2006, 217–223.
[3]	T. Asano, N. Katoh, H. Tamaki and T. Tokuyama, Angular Voronoi Diagram with Applications. Proc. International Symposium on Voronoi Diagram in Science and Engineering, Banff, Canada, 2006, 32–39.
[4]	F. Aurenhammer, Voronoi Diagrams–A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys,23 (1991), 345–405.
[5]	H. Edelsbrunner and N. Shah, Incremental topological flipping works for regular triangulations. Proc. of the 8th ACM Symp. on Computational Geometry 1992, 1992, 43–52. · Zbl 0840.68050
[6]	L.A. Freitag and P. Plassmann, Local optimization-based simplicial mesh untangling and improvement. Int. J. for Numerical Methods in Engineering,49 (2000), 109–125. · Zbl 0962.65098
[7]	D. Halperin and M. Sharir, Almost tight upper bounds for the single cell and zone problems in three dimensions. Proc. Symp. on Comput. Geom., 1994, 11–20.
[8]	LEDA: A library for Efficient Data Types and Algorithms. Algorithmic Solutions Software GmbH, Germany. · Zbl 0850.68170
[9]	J. Matousek, M. Sharir and E. Welzl, A Subexponential Bound for Linear Programming. Algorithmica,16 (1996), 498–516. · Zbl 0857.68119
[10]	S.A. Mitchell and S.A. Vavasis, Quality Mesh Generation in Three Dimensions. Proc. of the Eighth Annual Symp. on Computational Geometry, 1992, 212–221.
[11]	A. Okabe, B. Boots and K. Sugihara, Spatial Tessellations, Concepts and Applications of Voronoi Diagrams. John Wiley & Sons, New York, 1992. · Zbl 0877.52010
[12]	J.R. Shewchuk, Delaunay refinement algorithms for triangular mesh generation. Comput. Geom., Theory and Appl.,22 (2002), 21–74. · Zbl 1016.68139
[13]	K. Shimada and D.C. Gossard, Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing. Proc. of the Third Symposium on Solid Modeling and Applications, 1995, 409–419.