| Title: | Finding the convex hull of a dense set |
| DOI No: | 10.1142/9781860948534_0004 |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 37-44)
|
| Author(s): | Pavel Valtr
Department of Applied Mathematics and Institute for Computer Science, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
|
| Abstract: | For α > 0, a set A of n points in the plane is called α-dense, if the ratio between the maximum and the minimum distance in A is at most  . We show that the convex hull of an α-dense set of size n can be found in O(n log(min{n, α})) steps, which is worst-case asymptotically optimal in terms of n and α in the computation model of algebraic decision trees of a fixed order. We also show an asymptotically worst-case optimal output-sensitive bound O(n log(min{n, α, h})), where h is the number of vertices of the convex hull. |
| Full Text: | View full text in PDF format (410KB) |
| TOC: | Back to Table of Contents |
|
|
