On k-Hulls and Related Problems

1987/02/01 by Richard Cole, Micha Sharir, Chee Yap · 8 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Optimization and Packing Problems #Data Management and Algorithms #Hull #Hyperplane #Mathematics #Combinatorics #Set (abstract data type) #Dimension (graph theory) #Point (geometry) #Parametric statistics #Convex hull #Space (punctuation) #Discrete mathematics #Geometry #Computer science

paper · doi:10.1137/0216005

openalex publication_date 1987/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

For any set X of points (in any dimension) and any k = 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.

Citations

• Partitioning with two lines in the plane

Cited by

• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• The complexity and construction of many faces in arrangements of lines and of segments
• Applications of random sampling in computational geometry, II
• An Improved Bound for k-Sets in Three Dimensions
• Partitioning arrangements of lines I: An efficient deterministic algorithm
• Geometric Lower Bounds for Parametric Matroid Optimization
• Arrangement of lines [wikipedia]
• K-set (geometry) [wikipedia]