Finding the closest extreme vertex to a fixed point (Q1199551): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Bit serial addition trees and their applications / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The complexity of selection and ranking in X+Y and matrices with sorted columns / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3318088 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q4057549 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Parallel sorting algorithms for tightly coupled multiprocessors / rank | |||
Normal rank | |||
Latest revision as of 16:18, 16 May 2024
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
