An optimal real-time algorithm for planar convex hulls
From MaRDI portal
Publication:4190154
DOI10.1145/359131.359132zbMath0404.68069OpenAlexW1998115980MaRDI QIDQ4190154
Publication date: 1979
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359131.359132
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)
Related Items
Geometrical tools in classification, On determining the on-line minimax linear fit to a discrete point set in the plane, The convex hull of a set of convex polygons, On-line construction of the convex hull of a simple polyline, Finding the convex hull of a sorted point set in parallel, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Space-efficient planar convex hull algorithms, Connected component and simple polygon intersection searching, Fitting a two-joint orthogonal chain to a point set, Dynamic convex hulls under window-sliding updates, Convex hulls of spheres and convex hulls of disjoint convex polytopes, Maintenance of configurations in the plane, A linear time combinatorial algorithm to compute the relative orthogonal convex hull of digital objects, Steady-paced-output and fractional-on-line algorithms on a RAM, Relative convex hulls in semi-dynamic arrangements, Computing the convex hull in a hammock, Applications of a semi-dynamic convex hull algorithm, COMPUTING THE STRETCH FACTOR AND MAXIMUM DETOUR OF PATHS, TREES, AND CYCLES IN THE NORMED SPACE, Inconstancy of finite and infinite sequences, On finding the convex hull of a simple polygon, Quasi-Monotonic Sequences: Theory, Algorithms and Applications, Interval scheduling on related machines, An algorithm for discrete approximation by quasi-convex functions on \(R^m\), Applications of a semi-dynamic convex hull algorithm, Topological sweep of the complete graph, Connected component and simple polygon intersection searching, Lower bounds for maximal and convex layers problems, Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance, Two approaches to building time-windowed geometric data structures, Convex hull of a planar set of straight and circular line segments, The complexity of incremental convex hull algorithms in \(R^ d\)
