Given a set of n points P = {p1,p2,...,pn} in the plane, we show how to preprocess P such that for any query line segment L we can report in O(logn) time the smallest enclosing circle whose center is constrained to lie on L . The preprocessing time and space complexity are O(nlogn) and O(n) respectively. We then show how to use this data structure in order to compute the smallest enclosing circle of P whose center is restricted to lie in one of several polygons having a total of m edges, in O((m + n)logn) time, a significant improvement over previous known algorithms.
['Prosenjit Bose', 'Stefan Langerman', 'Sasanka Roy']
Smallest enclosing circle centered on a query line segment