Constrained minimum enclosing circle with center on a query line segment (Q924081): Difference between revisions
From MaRDI portal
Latest revision as of 20:43, 1 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Constrained minimum enclosing circle with center on a query line segment |
scientific article |
Statements
Constrained minimum enclosing circle with center on a query line segment (English)
0 references
27 July 2009
0 references
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)].
0 references
farthest point Voronoi diagram
0 references
minimum enclosing circle
0 references
algorithm
0 references