Applications of random sampling in computational geometry. II

From MaRDI portal

Publication:1823685

Jump to:navigation, search

DOI10.1007/BF02187740zbMath0681.68060OpenAlexW4254977685MaRDI QIDQ1823685

Peter W. Shor, Kenneth L. Clarkson

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131089

zbMATH Keywords

diameter convex hull computational geometry Voronoi diagrams Random sampling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sampling theory, sample surveys (62D05)

Related Items

Fast and efficient computation of additively weighted Voronoi cells for applications in molecular biology, Convex polygons made from few lines and convex decompositions of polyhedra, Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications, Robustness and Randomness, GEOMETRIC STREAMING ALGORITHM WITH A SORTING PRIMITIVE, APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS, COMPUTING THE DIAMETER OF A POINT SET, A Polynomial-Time Algorithm for Computing Shortest Paths of Bounded Curvature Amidst Moderate Obstacles, “The big sweep”: On the power of the wavefront approach to Voronoi diagrams, Geometric Packing under Nonuniform Constraints, On the geometric priority set cover problem, Clique-based separators for geometric intersection graphs, The projector algorithm: a simple parallel algorithm for computing Voronoi diagrams and Delaunay graphs, Optimal window queries on line segments using the trapezoidal search DAG, Computing the multicover bifiltration, Decomposition of Multiple Packings with Subquadratic Union Complexity, Approximating the k-Level in Three-Dimensional Plane Arrangements, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Unnamed Item, Constructive Polynomial Partitioning for Algebraic Curves in $\mathbb{R}^3$ with Applications, Geometric Streaming Algorithms with a Sorting Primitive, The Maximum Exposure Problem., Markov incremental constructions, On approximate range counting and depth, A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension, An efficient algorithm for the three-dimensional diameter problem, Unnamed Item, Entering and leaving \(j\)-facets, On a problem of Danzer, FURTHEST SITE ABSTRACT VORONOI DIAGRAMS, THE SHUFFLING BUFFER, RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS, Unnamed Item, Unnamed Item, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, An elementary algorithm for reporting intersections of red/blue curve segments, Bregman Voronoi diagrams, On lazy randomized incremental construction, A tail estimate for Mulmuley's segment intersection algorithm, Four results on randomized incremental constructions, Unnamed Item, GEOMETRIC OPTIMIZATION PROBLEMS OVER SLIDING WINDOWS, SUPERIMPOSING VORONOI COMPLEXES FOR SHAPE DEFORMATION, On a Problem of Danzer, A unified approach to tail estimates for randomized incremental construction, On range searching with semialgebraic sets, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time, Unnamed Item, Optimal Algorithms for Geometric Centers and Depth, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, Randomized incremental construction for the Hausdorff Voronoi diagram revisited and extended, Rounding Arrangements Dynamically, A Complete Implementation for Computing General Dimensional Convex Hulls, Dog Bites Postman, TetGen, a Delaunay-Based Quality Tetrahedral Mesh Generator, On range searching with semialgebraic sets, Point location among hyperplanes and unidirectional ray-shooting, On pseudo-disk hypergraphs, Castles in the air revisited, Faster geometric algorithms via dynamic determinant computation, Computing a single cell in the overlay of two simple polygons, \(k\)-violation linear programming, Abstract Voronoi diagrams revisited, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Almost tight upper bounds for lower envelopes in higher dimensions, Separating and shattering long line segments, Covering many or few points with unit disks, On the complexity of some basic problems in computational convexity. I. Containment problems, Derandomizing an output-sensitive convex hull algorithm in three dimensions, An introduction to randomization in computational geometry, Cuttings for disks and axis-aligned rectangles in three-space, From proximity to utility: a Voronoi partition of Pareto optima, Efficient and robust persistent homology for measures, The common exterior of convex polygons in the plane, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, Randomized incremental construction of simple abstract Voronoi diagrams in 3-space, Space-efficient planar convex hull algorithms, Erased arrangements of linear and convex decompositions of polyhedra, Space-efficient geometric divide-and-conquer algorithms, Topological relations between separating circles, Indexing moving points, Semi-algebraic Ramsey numbers, Computing farthest neighbors on a convex polytope., Optimal partition trees, Range minima queries with respect to a random permutation, and approximate range counting, On the union of cylinders in three dimensions, A kinetic triangulation scheme for moving points in the plane, Minimizing the error of linear separators on linearly inseparable data, Relative \((p,\varepsilon )\)-approximations in geometry, The overlay of minimization diagrams in a randomized incremental construction, An optimal generalization of the colorful Carathéodory theorem, Construction of \(\epsilon\)-nets, Combinatorial complexity bounds for arrangements of curves and spheres, Algebraic properties of location problems with one circular barrier., Approximation algorithms for maximum independent set of pseudo-disks, Certifying algorithms, Bold graph drawings, Union of random Minkowski sums and network vulnerability analysis, Euclidean minimum spanning trees and bichromatic closest pairs, Small-dimensional linear programming and convex hulls made easy, Points and triangles in the plane and halving planes in space, On \(k\)-sets in arrangements of curves and surfaces, An introduction to randomized algorithms, On disjoint concave chains in arrangements of (pseudo) lines, An upper bound on the number of planar \(K\)-sets, Randomized incremental construction of Delaunay and Voronoi diagrams, Repeated angles in the plane and related problems, On enclosing k points by a circle, Randomized quickhull, On counting pairs of intersecting segments and off-line triangle range searching, Applications of random sampling to on-line algorithms in computational geometry, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, How hard is half-space range searching?, Diameter, width, closest line pair, and parametric searching, On ray shooting in convex polytopes, Randomized incremental construction of abstract Voronoi diagrams, Dynamic point location in arrangements of hyperplanes, Four results on randomized incremental constructions, Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection, Fully dynamic Delaunay triangulation in logarithmic expected per operation, The number of edges of many faces in a line segment arrangement, Relative neighborhood graphs in three dimensions, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Fast linear expected-time algorithms for computing maxima and convex hulls, Computing hereditary convex structures, Seven fingers allow force-torque closure grasps on any convex polyhedron, Cutting hyperplanes for divide-and-conquer, On the randomized construction of the Delaunay tree, Algorithms for marketing-mix optimization, Higher-order Voronoi diagrams on triangulated surfaces, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Parallel geometric algorithms for multi-core computers, Partial-matching RMS distance under translation: combinatorics and algorithms, A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters, A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions, Two proofs for shallow packings, Depth of segments and circles through points enclosing many points: A note, Practical methods for shape fitting and kinetic data structures using coresets, Dynamic connectivity for axis-parallel rectangles, On the construction of abstract Voronoi diagrams, The widest k-dense corridor problems, Kinetic hanger, An approximate algorithm for computing multidimensional convex hulls, Efficient searching with linear constraints, An optimal convex hull algorithm in any fixed dimension, An invariant property of balls in arrangements of hyperplanes, A bound on local minima of arrangements that implies the upper bound theorem, Arrangements of oriented hyperplanes, On the union of fat wedges and separating a collection of segments by a line, \(k\)-sets and random hulls, Delaunay refinement algorithms for triangular mesh generation, Output sensitive and dynamic constructions of higher order Voronoi diagrams and levels in arrangements, On the sum of squares of cell complexities in hyperplane arrangements, The higher-order Voronoi diagram of line segments, Time-space trade-offs for triangulations and Voronoi diagrams, The maximum exposure problem, Abstract Voronoi diagram in 3-space, ``The big sweep: On the power of the wavefront approach to Voronoi diagrams, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Selecting distances in the plane, Computing a minimum-width square or rectangular annulus with outliers, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, On the union complexity of families of axis-parallel rectangles with a low packing number, A semi-algebraic version of Zarankiewicz's problem, Finding Pairwise Intersections Inside a Query Range, Time-Space Trade-offs for Triangulations and Voronoi Diagrams, Dynamic half-space range reporting and its applications, Largest \(j\)-simplices in \(n\)-polytopes, A new active convex hull model for image regions, A time-optimal parallel algorithm for three-dimensional convex hulls, On the \(k\)-colored rainbow sets in fixed dimensions, A crossing lemma for Jordan curves, On random cartesian trees, On geometric optimization with few violated constraints, Almost tight upper bounds for the single cell and zone problems in the three dimensions, Almost optimal set covers in finite VC-dimension, On topological changes in the Delaunay triangulation of moving points, The overlay of lower envelopes and its applications, Vertical decompositions for triangles in 3-space, Incremental topological flipping works for regular triangulations, Lines in space: Combinatorics and algorithms, The \(\varepsilon\)-\(t\)-net problem, On-line construction of the upper envelope of triangles and surface patches in three dimensions, An algorithm for constructing the convex hull of a set of spheres in dimension \(d\), Point location in zones of \(k\)-flats in arrangements, A deterministic algorithm for the three-dimensional diameter problem, Bipartite diameter and other measures under translation, Randomized geometric algorithms and pseudorandom generators, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Every Graph Admits an Unambiguous Bold Drawing, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, Untangling planar curves, Witnessed \(k\)-distance, On Center Regions and Balls Containing Many Points, Near-linear approximation algorithms for geometric hitting sets, Three problems about simple polygons, Convex hulls of spheres and convex hulls of disjoint convex polytopes, The 2-center problem in three dimensions, Improved approximation bounds for the minimum constraint removal problem, Random sampling with removal, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Coloring intersection hypergraphs of pseudo-disks, Constructing planar support for non-piercing regions, A simple algorithm for higher-order Delaunay mosaics and alpha shapes, Minimizing the diameter of a spanning tree for imprecise points, On a Question of Bourgain about Geometric Incidences, Manifold reconstruction using tangential Delaunay complexes, A tight lower bound for computing the diameter of a 3D convex polytope, A quick negative selection algorithm for one-class classification in big data era, 3D boundary recovery by constrained Delaunay tetrahedralization, Reprint of: Delaunay refinement algorithms for triangular mesh generation, Optimal deterministic shallow cuttings for 3-d dominance ranges, Finding pairwise intersections inside a query range, Faster approximate diameter and distance oracles in planar graphs, Classroom examples of robustness problems in geometric computations, A comparison of sequential Delaunay triangulation algorithms., Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\)., Local polyhedra and geometric graphs, On the complexity of the \(k\)-level in arrangements of pseudoplanes, Union of hypercubes and 3D Minkowski sums with random sizes, CONFLICT-FREE COLORINGS OF SHALLOW DISCS, All Farthest Neighbors in the Presence of Highways and Obstacles, Active-learning a convex body in low dimensions, On Kinetic Delaunay Triangulations, Randomized incremental construction of Delaunay triangulations of nice point sets, Polyhedral circuits and their applications, On circles enclosing many points, Constructing the convex hull of a partially sorted set of points, Cutting lemma and Zarankiewicz's problem in distal structures, Efficient randomized algorithms for some geometric optimization problems, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Dimensionality reduction for \(k\)-distance applied to persistent homology, Multi-core Implementations of Geometric Algorithms, A fast Las Vegas algorithm for triangulating a simple polygon, Two approaches to building time-windowed geometric data structures, Crossing patterns of semi-algebraic sets, Union and split operations on dynamic trapezoidal maps, Robot motion planning and the single cell problem in arrangements, Counting and representing intersections among triangles in three dimensions, On computing the diameter of a point set in high dimensional Euclidean space., Abstract Voronoi Diagrams from Closed Bisecting Curves, The \(k\)-nearest-neighbor Voronoi diagram revisited, Reporting intersecting pairs of convex polytopes in two and three dimensions, On constant factors in comparison-based geometric algorithms and data structures, On the complexity of randomly weighted multiplicative Voronoi diagrams, An Output-Sensitive Convex Hull Algorithm for Planar Objects, On the complexity of higher order abstract Voronoi diagrams, The maximum-level vertex in an arrangement of lines, Algebraic \(k\)-sets and generally neighborly embeddings

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1823685&oldid=14187724"