Abstract
For any set X of points (in any dimension) and any k equals 1, 2,. . . , we introduce the concept of the k-hull of X. The k-hull is the set of points p such that for any hyperplane containing p there are at least k points of X in each closed half-space determined by the hyperplane. Several computational problems related to k-hulls are studied here, including computing the k-hull and finding a point in the k-hull. Some of our algorithms are of interest in themselves because of the techniques employed; in particular, a 'parametric' searching technique is used in a nontrivial way.
Original language | English (US) |
---|---|
Pages (from-to) | 61-77 |
Number of pages | 17 |
Journal | SIAM Journal on Computing |
Volume | 16 |
Issue number | 1 |
DOIs | |
State | Published - 1987 |
ASJC Scopus subject areas
- General Computer Science
- General Mathematics