Finding the closest extreme vertex to a fixed point (Q1199551)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Finding the closest extreme vertex to a fixed point |
scientific article; zbMATH DE number 94471
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Finding the closest extreme vertex to a fixed point |
scientific article; zbMATH DE number 94471 |
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
0.86417854
0 references
0 references
0.8471943
0 references
0 references
0.82829964
0 references
0 references
0 references
