### 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

- Computer Science(all)
- Mathematics(all)

## Fingerprint Dive into the research topics of 'ON k-HULLS AND RELATED PROBLEMS.'. Together they form a unique fingerprint.

## Cite this

Cole, R., Sharir, M., & Yap, C. K. (1987). ON k-HULLS AND RELATED PROBLEMS.

*SIAM Journal on Computing*,*16*(1), 61-77. https://doi.org/10.1137/0216005