A note on the expected time required to construct the outer layer (Q1062448)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on the expected time required to construct the outer layer |
scientific article |
Statements
A note on the expected time required to construct the outer layer (English)
0 references
1985
0 references
The expected time E(T) of the standard divide-and-conquer algorithm for finding the outer layer of a set of points in the plane depends upon the distribution of the points. Under the mild assumption that the points are independent random vectors and have a common bounded density with compact support, it is shown that \(E(T)=O(n)\).
0 references
divide-and-conquer algorithm
0 references
outer layer of a set of points
0 references
independent random vectors
0 references
