Out-of-Roundness Problem Revisited
|
The properties and computation of the minimum radial separation (MRS) standard for out-of-roundness are discussed. Another standard out-of-roundness measurement called the minimum area difference (MAD) center is introduced. Although the two centers have different characteristics, the approach to finding both centers shares many commonalities. An O(n log n+k) time algorithm which is used to compute the MRS center is presented. It also computes the MAD center of a simple polygon G, where n is the number of vertices of G, and k is the number of intersection points of the medial axis and the farthest-neighbor Voronoi diagram of G. The relationship between MRS and MAD is discussed.
[1] 217A. Aggarwal, L. J. Guibas, J. Saxe, and P. Shor, "A linear time algorithm for computing the Voronoi diagram of a convex polygon,"Discrete Computational Geometry, vol. 4, pp. 591-604, 1989.
[2] B. Chazelle and H. Edelsbrunner, "An optimal algorithm for intersecting line segments in the plane," inProc. 29th Annu. Symp. Foundations of Computer Science, Oct. 1988, pp. 590-600.
[3] M. E. Dyer, "Linear time algorithms for two- and three-variable linear programs,"SIAM J. Comput., vol. 13, pp. 31-45, Feb. 1984.
[4] H. Ebara, N. Fukuyama, H. Nakano, and Y. Nakanishi, "Roundness algorithms using the Voronoi diagrams," submitted for publication.
[5] D. T. Lee, "Farthest neighbor Voronoi diagrams and applications," Dep. EECS, Northwestern Univ., Tech. Rep. 80-11-FC-04, Nov. 1980.
[6] D. T. Lee, "Medial axis transformation of a planar shape,"IEEE Trans. Pattern Anal. Machine Intell., vol. PAMI-4, no. 4, pp. 363-369, July 1982.
[7] S. J. Levy,Applied Geometric Tolerancing. TAD Products Corp., Section 11.
[8] H. G. Mairson and J. Stolfi, "Reporting and counting intersections between two sets of line segments," presented at the NATO Conf. Theoretical Foundations of Computer Graphics and CAD, July 1987.
[9] N. Megiddo, "Linear time algorithms for linear programming inR3and related problems,"SIAM J. Comput., vol. 12, no. 4, pp. 759-776, Nov. 1983.
[10] M. I. Shamos and D. Hoey, "Closest-point problems," inProc. 16th IEEE Symp. Foundations of Comput. Sci., Oct. 1975, pp. 151-162.
[11] G.T. Touissant, "Computing largest empty circles with location constraints,"Int. J. Comput. Inform. Sci., vol. 12, no. 5, pp. 347-358, 1983.
[12] C. K. Yap, "AnO(nlogn) algorithm for the Voronoi diagram of a set of simple curve segments," Courant Inst., New York Univ., New York, Tech. Rep., Oct. 1984.
Index Terms:
computational geometry; minimum area difference centre; minimum radial separation; out-of-roundness; polygon; intersection points; medial axis; farthest-neighbor Voronoi diagram; computational geometry
Citation:
V.B. Le, D.T. Lee, "Out-of-Roundness Problem Revisited," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 3, pp. 217-223, Mar. 1991, doi:10.1109/34.75510
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb