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.
BibTeX
@inproceedings{nielsen1996output,
  author = {Frank Nielsen},
  title = {{Output-Sensitive Peeling of Convex and Maximal Layers}},
  booktitle = {Inf. Process. Lett},
  year = {1996},
  url = {https://openreview.net/forum?id=14uwG7Oa-1Q},
}

Loading related content...

Figure