On k-Hulls and Related Problems
From MaRDI portal
Publication:3777473
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
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
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
