On k-Hulls and Related Problems

DOI10.1137/0216005zbMath0637.68074OpenAlexW2006769458WikidataQ56442902 ScholiaQ56442902MaRDI QIDQ3777473

Chee-Keng Yap, Micha Sharir, Richard John Cole

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216005

zbMATH Keywords

convex hullcomputational geometryparametric searchham sandwichk-set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items (39)

Halfspace range search: An algorithmic application of k-sets ⋮ Algorithms for ham-sandwich cuts ⋮ \(k\)-violation linear programming ⋮ Computing a centerpoint of a finite planar set of points in linear time ⋮ Partitioning point sets in arbitrary dimension ⋮ Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem ⋮ Divide and Conquer Method for k-Set Polygons ⋮ Cutting dense point sets in half ⋮ PARAMETRIC POLYMATROID OPTIMIZATION AND ITS GEOMETRIC APPLICATIONS ⋮ On geometric optimization with few violated constraints ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ \(k\)-capture in multiagent pursuit evasion, or the lion and the hyenas ⋮ Epsilon-nets for halfplanes ⋮ Minimizing the error of linear separators on linearly inseparable data ⋮ Partitioning arrangements of lines. I: An efficient deterministic algorithm ⋮ The complexity of hyperplane depth in the plane ⋮ Partitioning arrangements of lines. II: Applications ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ Methods for estimation of convex sets ⋮ Algorithms for bivariate zonoid depth ⋮ An upper bound on the number of planar \(K\)-sets ⋮ Output-sensitive peeling of convex and maximal layers ⋮ Concentration of the empirical level sets of Tukey's halfspace depth ⋮ Diameter, width, closest line pair, and parametric searching ⋮ Geometric medians ⋮ Algorithms for Radon partitions with tolerance ⋮ The complexity and construction of many faces in arrangements of lines and of segments ⋮ Approximate centerpoints with proofs ⋮ Point set stratification and Delaunay depth ⋮ Computing the least quartile difference estimator in the plane ⋮ Robust shape fitting via peeling and grating coresets ⋮ New lower bounds for Hopcroft's problem ⋮ Dynamic ham-sandwich cuts in the plane ⋮ New applications of random sampling in computational geometry ⋮ Applications of random sampling in computational geometry. II ⋮ Finding the \(\Theta \)-guarded region ⋮ Optimal Algorithms for Geometric Centers and Depth ⋮ On levels in arrangements and Voronoi diagrams ⋮ Order-\(k\) \(\alpha\)-hulls and \(\alpha\)-shapes

This page was built for publication: On k-Hulls and Related Problems