Finding the closest extreme vertex to a fixed point (Q1199551)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding the closest extreme vertex to a fixed point |
scientific article |
Statements
Finding the closest extreme vertex to a fixed point (English)
0 references
16 January 1993
0 references
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.
0 references
lower bounds
0 references
