11.30 a.m.
Smallest enclosing circle centered on a query line segment
Sasanka Roy
IISc, Bangalore.
08-07-09

---

Abstract

Given a set of n points P={p_1,p_2,...,p_n} in the plane, we show how to preprocess P such that for any query line segment L we can report in O(log n) time the smallest enclosing circle whose center is constrained to lie on L. The preprocessing time and space complexity are O(n log n) 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)log n) time, a significant improvement over previous known algorithms.