scientific article

zbMath0634.52001MaRDI QIDQ3772828

Herbert Edelsbrunner

Publication date: 1987

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

sortingcombinatorial geometryVoronoi diagramstime-complexityRadon theoremalgorithms in computational geometryarrangements of hyperplanes in Euclidean spacessearching Helly theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Exact enumeration problems, generating functions (05A15) Graph theory (including graph drawing) in computer science (68R10) Other designs, configurations (05B30) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Helly-type theorems and geometric transversal theory (52A35) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02)

Related Items (only showing first 100 items - show all)

\(\epsilon\)-nets and simplex range queries ⋮ Minimum polygonal separation ⋮ The complexity of cutting complexes ⋮ An algorithmic approach to some problems in terrain navigation ⋮ Spectral partitioning works: planar graphs and finite element meshes ⋮ Risk bounds for statistical learning ⋮ Topologically sweeping an arrangement ⋮ On the complexity of deriving position specific score matrices from positive and negative sequences ⋮ Parametric multiple sequence alignment and phylogeny construction ⋮ 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 ⋮ The power of pyramid decomposition in Normaliz ⋮ Exact computation of bivariate projection depth and the Stahel-Donoho estimator ⋮ Bottleneck partial-matching Voronoi diagrams and applications ⋮ Space-efficient algorithm for computing a centerpoint of a set of points in \(\mathbb{R}^2\) ⋮ 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 ⋮ New bounds on the unconstrained quadratic integer programming problem ⋮ 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 ⋮ Typechecking top-down XML transformations: Fixed input or output schemas ⋮ Randomized optimal algorithm for slope selection ⋮ Discrete and lexicographic Helly-type theorems ⋮ Efficient algorithms for maximum regression depth ⋮ 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 ⋮ 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 ⋮ Optimal complexity reduction of polyhedral piecewise affine systems ⋮ 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 ⋮ Computing zonoid trimmed regions of dimension \(d>2\) ⋮ The expected convex hull trimmed regions of a sample ⋮ Bisecton by global optimization revisited ⋮ The slab dividing approach to solve the Euclidean \(P\)-center problem ⋮ Bisecting a 4-connected graph with three resource sets ⋮ Depth of segments and circles through points enclosing many points: A note ⋮ A fast algorithm for the alpha-connected two-center decision problem ⋮ On regular vertices of the union of planar convex objects ⋮ A practical approximation algorithm for the LMS line estimator ⋮ Point set stratification and Delaunay depth ⋮ Dynamic ham-sandwich cuts in the plane ⋮ The analysis and the representation of balanced complex polytopes in 2D ⋮ A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation ⋮ New results on lower bounds for the number of \((\leq k)\)-facets ⋮ Smallest \(k\)-point enclosing rectangle and square of arbitrary orientation

This page was built for publication: