Finding the closest extreme vertex to a fixed point (Q1199551): Difference between revisions

Let \(S\) be a set of \(n\) points in the Euclidean plane and \(q\) a point not in \textit{S. Aggarwal} and \textit{M Hawrylycz} [Inf. Process. Lett. 31(6), 311-314 (1989; Zbl 0682.68038)] conjectured that finding the closest extreme vertex of \(CH(S)\) to \(q\) takes \(\Theta(n\log n)\) time, irrespective of the location of \(q\). We prove their conjecture.