An Algorithm for Smallest Enclosing Circle Problem of Planar Point Sets

详细信息    查看全文

• 关键词：Computational geometry ; Planar point sets ; Smallest enclosing circle ; Convex hull
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9786
• 期：1
• 页码：309-318
• 全文大小：717 KB
• 参考文献：1.Weckenmann, A., Eitzert, H., Garmer, M., Weber, H.: Functionality-oriented evaluation and sampling strategy in coordinate metrology. Precis. Eng. 17(4), 244–252 (1995)CrossRef
  2.Huang, X., Gu, P.: CAD-model based inspection of sculptured surfaces with datum. Int. J. Prod. Res. 36(5), 1351–1367 (1998)MathSciNet CrossRef MATH
  3.Elzinga, D.J., Hearn, D.W.: Geometrical solutions for some minimax location problems. Transp. Sci. 6(4), 379–394 (1972)MathSciNet CrossRef
  4.Oommen, B.J.: A learning automaton solution to the stochastic minimum spanning circle problem. IEEE Trans. Syst. Man Cybern. 16(4), 598–603 (1986)MathSciNet CrossRef
  5.Chakraborty, R.K., Chaudhuri, P.K.: Note on geometrical solution for some minimax location problems. Transp. Sci. 15(2), 164–166 (1981)MathSciNet CrossRef
  6.Oommen, B.J.: An efficient geometric solution to the minimum spanning circle problem. Oper. Res. 35(1), 80–86 (1987)MathSciNet CrossRef MATH
  7.Chrystal, G.: On the problem to construct the minimum circle enclosing N given points in the plane. Proc. Edinburgh Math. Soc. 3, 30–33 (1885)CrossRef MATH
  8.Li, X., Shi, Z.: The relationship between the minimum zone circle and the maximum inscribed circle and the minimum circumscribed circle. Precis. Eng. 33(3), 284–290 (2009)CrossRef
  9.Jywe, W.Y., Liu, C.H., Chen, C.K.: The min-max problem for evaluating the form error of a circle. Measurement 26(4), 777–795 (1999)CrossRef
  10.Shunmugam, M.S., Venkaiah, N.: Establishing circle and circular-cylinder references using computational geometric techniques. Int. J. Adv. Manuf. Technol. 51(1), 261–275 (2010)CrossRef
  11.Gadelmawla, E.S.: Simple and efficient algorithms for roundness evaluation from the coordinate measurement date. Measurement 43(2), 223–235 (2010)CrossRef
  12.Li, X., Shi, Z.: Development and application of convex hull in the assessment of roundness error. Int. J. Mach. Tools Manuf. 48(1), 135–139 (2008)CrossRef
  13.Lei, X., Zhang, C., Xue, Y., Li, J.: Roundness error evaluation algorithm based on polar coordinate transform. Measurement 44(2), 345–350 (2011)CrossRef
  14.Nair, K.P.K., Chandrasekaran, R.: Optimal location of a single service center of certain types. Naval Res. Logist. Q. 18, 503–510 (1971)MathSciNet CrossRef
  15.Chen, M.C., Tsai, D.M., Tseng, H.Y.: A stochastic optimization approach for roundness measurements. Pattern Recogn. Lett. 20(7), 707–719 (1999)CrossRef
  16.Goch, G., Lübke, K.: Tschebyscheff approximation for the calculation of maximum inscribed/minimum circumscribed geometry elements and form deviations. CIRP Ann. Manuf. Technol. 57(1), 517–520 (2008)CrossRef
  17.Anthony, G.T., Anthony, H.M., Bittner, B., Butler, B.P., Cox, M.G., Drieschner, R., et al.: Reference software for finding Chebyshev best-fit geometric elements. Precis. Eng. 19(1), 28–36 (1996)CrossRef
  18.Zhou, P.: An algorithm for determining the vertex of the convex hull. J. Beijing Inst. Technol. 13(1), 69–72 (1993)MATH
  19.Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Info. Proc. Lett. 1, 132–133 (1972)CrossRef MATH
  20.Zhou, P.: Computational geometry algorithm design and analysis, 4th edn, pp. 79–81. Tsinghua University Press, Beijing (2011)
  21.Klein, J.: Breve: a 3D environment for the simulation of decentralized systems and artificial life. In: Proceedings of Artificial Life VIII, the 8th International Conference on the Simulation and Synthesis of Living Systems. The MIT Press (2002)
  
• 作者单位：Xiang Li (22)
  M. Fikret Ercan (23)
  
  22. Department of Physics and Electronic Engineering, Hanshan Normal University, Chaozhou, 521041, China
  23. School of Electrical and Electronic Engineering, Singapore Polytechnic, 500 Dover Road, Singapore, 139651, Singapore
  
• 丛书名：Computational Science and Its Applications ¨C ICCSA 2016
• ISBN：978-3-319-42085-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9786

文摘

In this paper, a new computational algorithm is proposed for accurately determining the Smallest Enclosing Circle (SEC) of a finite point set (P) in plane. The set P that we are concerned here contains more than two non-collinear points which is a typical case. The algorithm basically searches for three particular points from P that forms the desired SEC of the set P. The SEC solution space of arbitrary P is uniform under this algorithm. The algorithmic mechanism is simple and it can be easily programmed. Our analysis proved that algorithm is robust and our empirical study verified its effectiveness. The computational complexity of the algorithm is found to be O(nlogn).