Back to my home page.
Output-sensitive peeling of convex and maximal layers
Frank Nielsen
Abstract:
We give an output-sensitive algorithm to compute the first k convex or maximal layers in O(n log hk)-time where
hk is the number of points participating in the first k layers.
Computing only the first k layers is interesting in various problems that arise in
computational geometry (k-sets and dually k-levels, k-hulls and dually k-belts), pattern recognition,
statistics, operations research, etc.
Key words: convex hulls, computational geometry.
Download the PS paper (included in the Ph. D. thesis)
The original publication is available at Elsevier Science (ScienceDirect).
http://dx.doi.org/10.1016/0020-0190(96)00116-0
Bibtex entry:
@Article{n-ospcml-1996,
author = {Frank Nielsen},
title = {Output-sensitive peeling of convex and maximal layers},
journal = {Information Processing Letters},
volume = {59},
number = {5},
year = {1996},
issn = {0020-0190},
pages = {255--259},
publisher = {Elsevier North-Holland, Inc.},
doi = {10.1016/0020-0190(96)00116-0}
}
Related publications:
Frank Nielsen,
Output-Sensitive Peeling of Convex and Maximal Layers
Information Processing Letters (Elsevier Science),
Volume 59, pp. 255-259, 1996.
© Copyright notice.
Last updated, 2003.