Output-sensitive peeling of convex and maximal layers

Frank Nielsen

(pdf) (pdf) (pdf) (pdf) (pdf)

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 paper 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}
 }
Last updated, 2020.