Computing the Closest Point to a Circle
Pinaki Mitra, Asish Kumar Mukhopadhyay, S. Venugopal Rao · Canadian Conference on Computational Geometry · 2003
In this paper we consider the problem of computing the closest point to the boundary of a circle among a set S of n points. We present two algorithms to solve this problem. One algorithm runs in O(n 3 ) preprocessing time and space and O(log 2 n) query time. The other algorithm runs in O(n 1+� ) preprocessing time and O(n log n) space and O(n 2/3+� ) query time. Thus we exhibit a trade-off between preprocessing and query times For dimensions d ≥ 3 we present an algorithm with