On k-Hulls and Related Problems
SIAM Journal on Computing1987Vol. 16(1), pp. 61–77
Citations Over TimeTop 10% of 1987 papers
Abstract
For any set X of points (in any dimension) and any $k = 1,2, \cdots $, 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.
Related Papers
- → The hyperplanes of DH(5, q 2)(2008)19 cited
- → Searching for features defined by hyperplanes(1996)22 cited
- → Finding little hyperplanes in bigger ones(1981)1 cited
- Parallel Free Arrangements(2008)
- → Drawbacks of the Present System of Unified Requirements for Ship Hull Global Strength and Potential Ways to Rectify Them(2000)