On the convex layers of a planar set

DOI10.1109/TIT.1985.1057060zbMath0573.68035OpenAlexW2048493433MaRDI QIDQ3691073

Bernard Chazelle

Publication date: 1985

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1109/tit.1985.1057060

zbMATH Keywords

convex hullconvex polygonsoptimal algorithmplanar point setplanar point location problemdepth of a query point

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Polyhedra and polytopes; regular figures, division of spaces (51M20) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99) Polytopes and polyhedra (52Bxx)

Related Items (51)

Expected size of random Tukey layers and convex layers ⋮ Simplification of surface parametrizations --a lattice polygon approach ⋮ Dynamic coresets ⋮ Novel concave hull-based heuristic algorithm for TSP ⋮ Selection and sorting in totally monotone arrays ⋮ Quadrangulations of planar sets ⋮ Onion polygonizations ⋮ In-place algorithms for computing (Layers of) maxima ⋮ PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS ⋮ Drawing the almost convex set in an integer grid of minimum size ⋮ Nearest-neighbor searching under uncertainty. I ⋮ Characterizing and efficiently computing quadrangulations of planar point sets ⋮ The centroid of points with approximate weights ⋮ Likelihood-based inference for exponential-family random graph models via linear programming ⋮ Exact and heuristic solutions for the prize‐collecting geometric enclosure problem ⋮ On bounded leg shortest paths problems ⋮ A faster algorithm for the maximum weighted tardiness problem ⋮ Unnamed Item ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ Relative convex hulls in semi-dynamic arrangements ⋮ Algorithms for bivariate zonoid depth ⋮ Efficient generation of simple polygons for characterizing the shape of a set of points in the plane ⋮ Spiral Serpentine Polygonization of a Planar Point Set ⋮ Output-sensitive peeling of convex and maximal layers ⋮ Multilist layering: Complexity and applications ⋮ Largest and smallest area triangles on imprecise points ⋮ Revisiting Shao and Sokal's \(B_2\) index of phylogenetic balance ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Upper envelope onion peeling ⋮ Geometric medians ⋮ On the red/blue spanning tree problem ⋮ Triangulating with high connectivity. ⋮ Angle-restricted tours in the plane. ⋮ Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications ⋮ Applications of a semi-dynamic convex hull algorithm ⋮ Upper envelope onion peeling ⋮ New estimates for convex layer numbers ⋮ A new variational approach based on level-set function for convex hull problem with outliers ⋮ Constructing the convex hull of a partially sorted set of points ⋮ Point set stratification and Delaunay depth ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Algorithms for optimal outlier removal ⋮ Grid peeling and the affine curve-shortening flow ⋮ Lower bounds for maximal and convex layers problems ⋮ Two approaches to building time-windowed geometric data structures ⋮ Finding the \(\Theta \)-guarded region ⋮ The layer number of \(\alpha \)-evenly distributed point sets ⋮ An efficient algorithm for enumeration of triangulations ⋮ On embedding an outer-planar graph in a point set ⋮ Four-connected triangulations of planar point sets ⋮ A fixed-parameter algorithm for guarding 1.5D terrains

This page was built for publication: On the convex layers of a planar set