Fast computation of smallest enclosing circle with center on a query line segment

详细信息    查看全文

• 作者：Arindam Karmakar ; Sasanka Roy ; S ; ip Das
• 关键词：1-center problem ; Furthest point Voronoi diagram ; Geometric duality ; Computational geometry ; Algorithms
• 刊名：Information Processing Letters
• 出版年：2008
• 出版时间：30 November 2008
• 年：2008
• 卷：108
• 期：6
• 页码：343-346
• 全文大小：221 K

文摘

Here we propose an efficient algorithm for computing the smallest enclosing circle whose center is constrained to lie on a query line segment. Our algorithm preprocesses a given set of n points P={p₁,p₂,…,p_n} such that for any query line or line segment L, it efficiently locates a point c on L that minimizes the maximum distance among the points in P from c. Roy et al. [S. Roy, A. Karmakar, S. Das, S.C. Nandy, Constrained minimum enclosing circle with center on a query line segment, in: Proc. of the 31st Mathematical Foundation of Computer Science, 2006, pp. 765–776] have proposed an algorithm that solves the query problem in O(log²n) time using O(nlogn) preprocessing time and O(n) space. Our algorithm improves the query time to O(logn); but the preprocessing time and space complexities are both O(n²).