Constrained minimum enclosing circle with center on a query line segment (Q924081): Difference between revisions

The authors consider the online query version of the minimum enclosing circle problem proposed by \textit{N. Megiddo} [SIAM J. Comput. 12, 759--776 (1983; Zbl 0521.68034)]. Given a point set \(P\) in the plane, a preprocessing algorithm is suggested such that given any arbitrary line segment \(L\), the smallest enclosing circle of \(P\) with center on \(L\) can be reported efficiently. First, a line as query object is considered and the corresponding algorithm is proposed. Next, it is shown that the same method works when the query object is a line segment. Moreover, the algorithm can be used for solved a related problem: Given \(P\) and a set of simple polygons, compute the smallest enclosing circle of \(P\) whose center lies inside one of these polygons. A preliminary version of this paper was published by the same authors [Lecture Notes in Computer Science 4162, 765--776 (2006; Zbl 1132.68797)].