ON k-HULLS AND RELATED PROBLEMS.

Richard Cole, Micha Sharir, Chee K. Yap

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)61-77
Number of pages17
JournalSIAM Journal on Computing
Volume16
Issue number1
DOIs
StatePublished - 1987

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

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

Cite this