Name
Title | ||
|---|---|---|
On the complexity of convex hull algorithms if rotational minima can be found very fast |
Abstract | ||
|---|---|---|
For a large class of time functionsT, we show the following: Assuming that there is some parallel processor which requiresθ(T(j)) time units when searching the minimum amongj arbitrary points with respect to an arbitrary rotational ordering. Then the planar Convex Hull Problem forn points is of the complexityθ(nT(n)). |
Year | DOI | Venue |
|---|---|---|
1988 | 10.1007/BF01928920 | Zeitschrift für Operations-Research |
Keywords | Field | DocType |
Convex Hull, Jarvis' March, Gift-Wrapping-Algorithm, Trees, Sorting, Parallel Networks | Orthogonal convex hull,Combinatorics,Convex hull algorithms,Convex combination,Convex set,Convex hull,Convex polytope,Output-sensitive algorithm,Gift wrapping algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 3 | 1432-5217 |
Citations | PageRank | References |
1 | 0.56 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| U. Huckenbeck | 1 | 11 | 2.17 |