Constrained minimum enclosing circle with center on a query line segment

详细信息    查看全文

• 作者：Sasanka Roy ; Arindam Karmakar ; S ; ip Das ; Subhas C. N ; y
• 关键词：Farthest point Voronoi diagram ; Minimum enclosing circle
• 刊名：Computational Geometry
• 出版年：2009
• 出版时间：August 2009
• 年：2009
• 卷：42
• 期：6-7
• 页码：632-638
• 全文大小：217 K

文摘

In this paper, we will study the problem of locating the center of the smallest enclosing circle of a set P of n points, where the center is constrained to lie on a query line segment. The preprocessing time and space complexities of our proposed algorithm are O(nlogn) and O(n) respectively; the query time complexity is O(log²n).