Publication:3772828
From MaRDI portal
zbMath0634.52001MaRDI QIDQ3772828
Publication date: 1987
sorting; combinatorial geometry; Voronoi diagrams; time-complexity; Radon theorem; algorithms in computational geometry; arrangements of hyperplanes in Euclidean spaces; searching Helly theorem
68Q25: Analysis of algorithms and problem complexity
68P10: Searching and sorting
05A15: Exact enumeration problems, generating functions
68R10: Graph theory (including graph drawing) in computer science
05B30: Other designs, configurations
68-02: Research exposition (monographs, survey articles) pertaining to computer science
52A35: Helly-type theorems and geometric transversal theory
52-02: Research exposition (monographs, survey articles) pertaining to convex and discrete geometry
Related Items
The complexity and construction of many faces in arrangements of lines and of segments, The complexity of many cells in arrangements of planes and related problems, Proximate point searching, The legacy of automatic mesh generation from solid modeling, An incremental algorithm for Betti numbers of simplicial complexes on the 3-sphere, Why is the 3D Delaunay triangulation difficult to construct?, Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions, A pseudo-algorithmic separation of lines from pseudo-lines, \(\varepsilon\)-approximations of \(k\)-label spaces, Fast randomized parallel methods for planar convex hull construction, On intersecting a point set with Euclidean balls, On counting pairs of intersecting segments and off-line triangle range searching, Towards exact geometric computation, Geometric pattern matching under Euclidean motion, Range searching with efficient hierarchical cuttings, An upper bound for conforming Delaunay triangulations, On ray shooting in convex polytopes, A theorem on the average number of subfaces in arrangements and oriented matroids, The power of parallel projection, Four results on randomized incremental constructions, Algorithms for weak and wide separation of sets, Antipodal graphs and oriented matroids, Linear time algorithms for some separable quadratic programming problems, Geometric Knapsack problems, Optimal slope selection via expanders, The combinatorial structure of random polytopes, Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems, Constructions and complexity of secondary polytopes, A deterministic view of random sampling and its use in geometry, Construction of Voronoi diagrams in the plane by using maps, Computing a sweeping-plane in regular (``general) position: A numerical and a symbolic solution, An acyclicity theorem for cell complexes in d dimensions, Variations on the theme of repeated distances, On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces, A dual approach to detect polyhedral intersections in arbitrary dimensions, Order-k Voronoi diagrams of sites with additive weights in the plane, Toughness and Delaunay triangulations, Dynamic partition trees, Using Gale transforms in computational geometry, Construction of three-dimensional Delaunay triangulations using local transformations, A new representation of orientable 2-manifold polygonal surfaces for geometric modelling, Spectral partitioning works: planar graphs and finite element meshes, Risk bounds for statistical learning, On the complexity of deriving position specific score matrices from positive and negative sequences, Parametric multiple sequence alignment and phylogeny construction, On the angle restricted nearest neighbor problem, Storing line segments in partition trees, Realizability of Delaunay triangulations, Partitioning arrangements of lines. I: An efficient deterministic algorithm, Construction of \(\epsilon\)-nets, Efficient binary space partitions for hidden-surface removal and solid modeling, An optimal parallel algorithm for linear programming in the plane, Algorithms for high dimensional stabbing problems, Combinatorial complexity bounds for arrangements of curves and spheres, Covering orthogonal polygons with star polygons: The perfect graph approach, The upper envelope of piecewise linear functions: Tight bounds on the number of faces, The upper envelope of piecewise linear functions: Algorithms and applications, \(\epsilon\)-nets and simplex range queries, Minimum polygonal separation, The complexity of cutting complexes, An algorithmic approach to some problems in terrain navigation, Topologically sweeping an arrangement, Submodularity and the traveling salesman problem, Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm, Compaction and separation algorithms for non-convex polygons and their applications, Parallel computation of distance transforms, Bounding the number of \(k\)-faces in arrangements of hyperplanes, The complexity of point configurations, Cutting hyperplane arrangements, 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, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Bisections and ham-sandwich cuts of convex polygons and polyhedra, A role of lower semicontinuous functions in the combinatorial complexity of geometric problems, On \(k\)-sets in arrangements of curves and surfaces, A basis enumeration algorithm for linear systems with geometric applications, Improved complexity bounds for location problems on the real line, Randomized optimal algorithm for slope selection, Satisfying general proximity/similarity queries with metric trees, On disjoint concave chains in arrangements of (pseudo) lines, An upper bound on the number of planar \(K\)-sets, Almost tight bounds for \(\epsilon\)-nets, Tiling polygons with parallelograms, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Randomized incremental construction of Delaunay and Voronoi diagrams, Finding minimum area \(k\)-gons, How to find Steiner minimal trees in Euclidean \(d\)-space, Optimal parallel algorithms for point-set and polygon problems, Counting facets and incidences, A new representation and algorithm for constructing convex hulls in higher dimensional spaces, Applications of random sampling to on-line algorithms in computational geometry, Finding stabbing lines in 3-space, Counting and cutting cycles of lines and rods in space, 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, Delaunay triangulations in three dimensions with finite precision arithmetic, The convergence rate of the sandwich algorithm for approximating convex functions, Reporting points in halfspaces, Intersection queries in sets of disks, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines., Tutte's barycenter method applied to isotopies, Decomposable multi-parameter matroid optimization problems., Norm-based approximation in multicriteria programming., The complexity of hyperplane depth in the plane, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Placing two disks in a convex polygon, Efficient searching with linear constraints, \(l_\infty\)-approximation via subdominants., Convex polyhedra in \(\mathbb{R}^3\) spanning \(\Omega(n^{4/3})\) congruent triangles, Improving continuity of Voronoi-based interpolation over Delaunay spheres, Geometry of the space of phylogenetic trees, Regular triangulations of dynamic sets of points, Estimating the number of vertices of a polyhedron, Collision detection algorithm of a continuous type using spherical extreme vertex diagrams, Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, Recent progress in exact geometric computation, Facility location problems with uncertainty on the plane, On the total weight of arrangements of halfplanes, Constructing arrangements optimally in parallel, Representing geometric structures in \(d\) dimensions: Topology and order, Nested cones and onion skins, Constructing the convex hull of a partially sorted set of points, On vertical ray shooting in arrangements, An efficient algorithm for determining the extreme vertices of a moving 3D convex polyhedron with respect to a plane, Undesirable facility location with minimal covering objectives, Combinatorial optimization and small polytopes, Optimal output-sensitive convex hull algorithms in two and three dimensions, Output-sensitive results on convex hulls, extreme points, and related problems, New lower bounds for Hopcroft's problem, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Congruence, similarity, and symmetries of geometric objects, A note on the Papadimitriou-Silverberg algorithm for planning optimal piecewise-linear motion of a ladder, Applications of random sampling in computational geometry. II, Quasi-optimal range searching in spaces of finite VC-dimension, Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros, A probabilistic result on multi-dimensional Delaunay triangulations, and its application to the 2D case, Complexity of projected images of convex subdivisions, Counting problems relating to a theorem of Dirichlet, Probing the arrangement of hyperplanes, Robot motion planning and the single cell problem in arrangements, A lower bound on Voronoi diagram complexity., On the complexity of one-shot translational separability., Decision trees: Old and new results., Algorithmic results for ordered median problems, Dynamic maintenance and visualization of molecular surfaces., Monotone paths in line arrangements, Sets of lines and cutting out polyhedral objects, The Safari interface for visualizing time-dependent volume data using iso-surfaces and contour spectra, On depth and deep points: A calculus., On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, An efficient \(k\) nearest neighbors searching algorithm for a query line., Separability by two lines and by nearly straight polygonal chains, Triangular range counting query in 2D and its application in finding \(k\) nearest neighbors of a line segment, Graph Laplacians, nodal domains, and hyperplane arrangements, Set membership identification of nonlinear systems, Dynamic half-space range reporting and its applications, Tight upper bounds for the discrepancy of half-spaces, Assembly sequences for polyhedra, Asymptotic speed-ups in constructive solid geometry, Staircase visibility and computation of kernels, A linear-time algorithm for constructing a circular visibility diagram, Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains, Separation and approximation of polyhedral objects, On a class of \(O(n^ 2)\) problems in computational geometry, Almost tight upper bounds for the single cell and zone problems in the three dimensions, Efficient piecewise-linear function approximation using the uniform metric, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, Parallel algorithms for arrangements, Sweep methods for parallel computational geometry, The overlay of lower envelopes and its applications, Incremental topological flipping works for regular triangulations, Lines in space: Combinatorics and algorithms, Improved heuristics for the minimum weight triangulation problem, Voronoi-like partition of lattice in cellular automata, Generalized hidden surface removal, Algorithms for generalized halfspace range searching and other intersection searching problems, Computing half-plane and strip discrepancy of planar point sets, Point location in zones of \(k\)-flats in arrangements, The exact fitting problem in higher dimensions, Finding Hamiltonian cycles in Delaunay triangulations is NP-complete, Reverse search for enumeration, Connected component and simple polygon intersection searching, Maxpolynomial equations, On stable line segments in all triangulations of a planar point set, The number of extreme triples of a planar point set, Mixed-volume computation by dynamic lifting applied to polynomial system solving, Shadow-boundaries of convex bodies, On Voronoi diagrams in the \(L_p\)-metric in \(\mathbb{R}^D\)., Optimal tetrahedralization of the 3D-region ``between a convex polyhedron and a convex polygon, Input-output decoupling for linear systems with nonlinear uncertain structure, On absolute stability analysis by polyhedral Lyapunov functions, Three-dimensional convex hull as a fruitful source of diagrams, Lower bounds for off-line range searching, The searching over separators strategy to solve some NP-hard problems in subexponential time, Ray shooting on triangles in 3-space, Selecting distances in the plane, Weaving patterns of lines and line segments in space, Algorithms for projecting points to give the most uniform distribution with applications to hashing, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, Fast algorithms for greedy triangulation, Optimal time bounds for some proximity problems in the plane, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Transitions in geometric minimum spanning trees, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, Efficient partition trees, Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs, Upper envelope onion peeling, Minimizing the sum of diameters efficiently, The colored Tverberg's problem and complexes of injective functions, On computing the exact value of dispersion of a sequence, Hamiltonian triangulations and circumscribing polygons of disjoint line segments, Convexity preserving interpolation and Powell-Sabin elements, Geometric medians, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Parallel methods for visibility and shortest-path problems in simple polygons, Stacks, queues, and deques with order-statistic operations, The slab dividing approach to solve the Euclidean \(P\)-center problem, The upper envelope of Voronoi surfaces and its applications, Interval probability propagation, Degree constrained tree embedding into points in the plane, Cutting hyperplanes for divide-and-conquer, On the zone of a surface in a hyperplane arrangement, On the randomized construction of the Delaunay tree, An efficient algorithm for finding the CSG representation of a simple polygon, On arrangements of Jordan arcs with three intersections per pair, Implicitly representing arrangements of lines or segments, A computational basis for higher-dimensional computational geometry and applications, On some geometric selection and optimization problems via sorted matrices, Isolating points by lines in the plane, Finding minimum area simple pentagons, The catline for deep regression, A nearly parallel algorithm for the Voronoi diagram of a convex polygon, Detecting geometric infeasibility, The widest k-dense corridor problems, Guarding galleries where no point sees a small area., Noise-tolerant parallel learning of geometric concepts, Stabbing information of a simple polygon, Solving restricted line location problems via a dual interpretation, Halfspace depth and regression depth characterize the empirical distribution, An approximate algorithm for computing multidimensional convex hulls, Bipartite embeddings of trees in the plane, A software package of algorithms and heuristics for disjoint paths in \textit{Pla}nar \textit{Net}works, A comment on a minmax location problem, Numerical stability of a convex hull algorithm for simple polygons, 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, A parallel algorithm for constructing projection polyhedra, The rooted tree embedding problem into points in the plane, On the union of fat wedges and separating a collection of segments by a line, Representing polyhedra: Faces are better than vertices, Algorithms for ordering unorganized points along parametrized curves, Enumerating extreme points of a highly degenerate polytope, A sweepline algorithm to solve the two-center problem, On the sum of squares of cell complexities in hyperplane arrangements, A workbench for computational geometry, Provably good mesh generation, On range searching with semialgebraic sets, Algorithms for ham-sandwich cuts, Point location among hyperplanes and unidirectional ray-shooting, Extremal polygon containment problems, Point placement algorithms for Delaunay triangulation of polygonal domains, Efficient ray shooting and hidden surface removal, Crossing families, On stabbing lines for convex polyhedra in 3D, Optimality of the Delaunay triangulation in \(\mathbb{R}^ d\), On lines missing polyhedral sets in 3-space, \(k\)-violation linear programming, Many-face complexity in incremental convex arrangements, Computing convex hull in a floating point arithmetic, Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements, Counting triangle crossings and halving planes, Computing a centerpoint of a finite planar set of points in linear time, On the complexity of some basic problems in computational convexity. I. Containment problems, Better lower bounds on detecting affine and spherical degeneracies, On minimum and maximum spanning trees of linearly moving points, Derandomizing an output-sensitive convex hull algorithm in three dimensions, Localization and classification based on projections, Computing depth contours of bivariate point clouds, On nearest-neighbor graphs, Practical issues on the projection of polyhedral sets, Graph-theoretical conditions for inscribability and Delaunay realizability, How good are convex hull algorithms?, Optimal and approximate bottleneck Steiner trees, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees, The common exterior of convex polygons in the plane, Optimal, output-sensitive algorithms for constructing planar hulls in parallel, On the number of simplicial complexes in \(\mathbb{R}^ d\), Three-dimensional unstructured mesh generation. I: Fundamental aspects of triangulation and point creation, Improved upper bounds for approximation by zonotopes, Erased arrangements of linear and convex decompositions of polyhedra, On fat partitioning, fat covering and the union size of polygons, Combinatorial aspects of geometric graphs, Compactifications of the configuration space of six points of the projective plane and fundamental solutions of the hypergeometric system of type \((3,6)\), A lower bound for randomized algebraic decision trees, Randomization and the computational power of analytic and algebraic decision trees, Illumination by floodlights, PAC-learning from general examples, Reporting the crossing-free segments of a complete geometric graph, Combinatorial Properties of One-Dimensional Arrangements, A LIBRARY FOR DOING POLYHEDRAL OPERATIONS, Optimal grid representations, Modélisation géométrique de la faisabilité de plusieurs mélanges, Modélisation et optimisation numérique pour la reconstruction d'un polyèdre à partir de son image gaussienne généralisée, An augmented spatial digital tree algorithm for contact detection in computational mechanics, The minimum expectation selection problem, Unnamed Item, BIFURCATIONS OF VORONOI DIAGRAMS AND ITS APPLICATION TO BRAID THEORY, Robot motion planning, Curvature approximation of 3D manifolds in 4D space, Curvature approximation of 3D manifolds in 4D space, Paul Erdős, 1913-1996, Sweeps, arrangements and signotopes, A simple proof of an estimate for the approximation of the Euclidean ball and the Delone triangulation numbers, On the number of regular vertices of the union of Jordan regions, Dynamically maintaining the widest \(k\)-dense corridor, Voronoi diagrams on piecewise flat surfaces and an application to biological growth, Matching colored points in the plane: Some new results, Sequential incorporation of imprecise information in multiple criteria decision processes, On \(\beta\)-skeleton as a subgraph of the minimum weight triangulation, Two-variable linear programming in parallel, Algorithms for generalized halfspace range searching and other intersection searching problems, Voronoi diagrams over dynamic scenes, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Edge insertion for optimal triangulations, Topes of oriented matroids and related structures, Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem, Opposite-quadrant depth in the plane, Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem, On some monotone path problems in line arrangements, Suspension bridge effect -- a consideration about numerical precision of the natural neighbor interpolation, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Locating an obnoxious plane, Fast Delaunay triangulation in three dimensions, A robust algorithm for bisecting a triconnected graph with two resource sets, Harmonic functions for quadrilateral remeshing of arbitrary manifolds, The predicates of the Apollonius diagram: algorithmic analysis and implementation, Identification of piecewise affine systems based on statistical clustering technique, Symbolic treatment of geometric degeneracies, On the number of halving planes, Cyclic schedules for r irregularity occurring events, Computation of a penetration measure between 3D convex polyhedral objects for collision detection, Spanning trees with low crossing number, Increasing integer sequences and Goldbach's conjecture, Visibility graphs and obstacle-avoiding shortest paths, Conditions for regular $B$-spline curves and surfaces, Delaunay versus max-min solid angle triangulations for three-dimensional mesh generation, Nonlinear system stability boundary approximation by polytopes in state space†
