Constructing Arrangements of Lines and Hyperplanes with Applications
From MaRDI portal
Publication:3740283
DOI10.1137/0215024zbMath0603.68104DBLPjournals/siamcomp/EdelsbrunnerOS86OpenAlexW2120934134WikidataQ56442905 ScholiaQ56442905MaRDI QIDQ3740283
Raimund Seidel, Joseph O'Rourke, Herbert Edelsbrunner
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0215024
configurationscombinatorial geometryoptimal algorithmcomputational geometryVoronoi diagramsgeometric transformationcell complex
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polyhedra and polytopes; regular figures, division of spaces (51M20) Other problems of combinatorial convexity (52A37) Polytopes and polyhedra (52Bxx)
Related Items (only showing first 100 items - show all)
Halfspace range search: An algorithmic application of k-sets ⋮ Iterated nearest neighbors and finding minimal polytopes ⋮ The complexity of cells in three-dimensional arrangements ⋮ Voronoi diagrams and arrangements ⋮ Identification of points using disks ⋮ A linear optimization oracle for zonotope computation ⋮ Covering grids and orthogonal polygons with periscope guards ⋮ A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis ⋮ An approximation algorithm for least median of squares regression ⋮ Visibility of disjoint polygons ⋮ Edge-skeletons in arrangements with applications ⋮ Point set pattern matching in \(d\)-dimensions ⋮ Polygonizations of point sets in the plane ⋮ Better lower bounds on detecting affine and spherical degeneracies ⋮ Optimal separable partitioning in the plane ⋮ Recognising polytopical cell complexes and constructing projection polyhedra ⋮ Lower bounds on moving a ladder in two and three dimensions ⋮ Straight skeletons and mitered offsets of nonconvex polytopes ⋮ Hamiltonicity and colorings of arrangement graphs ⋮ Parallel algorithms for arrangements ⋮ Verifiable implementations of geometric algorithms using finite precision arithmetic ⋮ Witness Gabriel graphs ⋮ Computing half-plane and strip discrepancy of planar point sets ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ Topologically sweeping an arrangement ⋮ Shadow-boundaries of convex bodies ⋮ Erased arrangements of linear and convex decompositions of polyhedra ⋮ Illumination by floodlights ⋮ Finding constrained and weighted Voronoi diagrams in the plane ⋮ All-maximum and all-minimum problems under some measures ⋮ Flip distance between triangulations of a simple polygon is NP-complete ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ Approximation algorithms for free-label maximization ⋮ On colouring point visibility graphs ⋮ Efficient view point selection for silhouettes of convex polyhedra ⋮ Graph problems arising from parameter identification of discrete dynamical systems ⋮ Computing optimal islands ⋮ An optimal algorithm for the boundary of a cell in a union of rays ⋮ Searching for empty convex polygons ⋮ From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices ⋮ Shape matching by random sampling ⋮ Triangulating a nonconvex polytope ⋮ A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems ⋮ Algorithms for high dimensional stabbing problems ⋮ Combinatorial complexity bounds for arrangements of curves and spheres ⋮ The generic combinatorial algorithm for image matching with classes of projective transformations ⋮ Partitioning arrangements of lines. II: Applications ⋮ Sorting weighted distances with applications to objective function evaluations in single facility location problems. ⋮ New bounds on the unconstrained quadratic integer programming problem ⋮ Bounding the number of \(k\)-faces in arrangements of hyperplanes ⋮ The complexity of point configurations ⋮ Cutting hyperplane arrangements ⋮ Computing solutions of the multiclass network equilibrium problem with affine cost functions ⋮ Counting \(k\)-subsets and convex \(k\)-gons in the plane ⋮ Efficient algorithms for maximum regression depth ⋮ Arrangements of curves in the plane --- topology, combinatorics, and algorithms ⋮ Zone theorem for arrangements in dimension three ⋮ Finding minimum area \(k\)-gons ⋮ Algorithms for deciding the containment of polygons ⋮ The farthest point Delaunay triangulation minimizes angles ⋮ Reaching a goal with directional uncertainty ⋮ Largest and smallest area triangles on imprecise points ⋮ Counting convex \(k\)-gons in planar point sets ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Geometric matching algorithms for two realistic terrains ⋮ A theorem on the average number of subfaces in arrangements and oriented matroids ⋮ A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra ⋮ Algorithms for weak and wide separation of sets ⋮ The number of edges of many faces in a line segment arrangement ⋮ Geometric medians ⋮ New complexity bounds for image matching under rotation and scaling ⋮ Algorithms for marketing-mix optimization ⋮ Witness (Delaunay) graphs ⋮ Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm ⋮ Finding all pure strategy Nash equilibria in a planar location game ⋮ 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 ⋮ Polyhedral circuits and their applications ⋮ Topological sweep of the complete graph ⋮ Constructing arrangements optimally in parallel ⋮ Representing geometric structures in \(d\) dimensions: Topology and order ⋮ A new polynomially solvable class of quadratic optimization problems with box constraints ⋮ Implicitly representing arrangements of lines or segments ⋮ Constructions and complexity of secondary polytopes ⋮ A deterministic view of random sampling and its use in geometry ⋮ A dual approach to detect polyhedral intersections in arbitrary dimensions ⋮ New applications of random sampling in computational geometry ⋮ Applications of random sampling in computational geometry. II ⋮ Median hyperplanes in normed spaces -- a survey ⋮ Stabbing information of a simple polygon ⋮ A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Robot motion planning and the single cell problem in arrangements ⋮ Some results on point visibility graphs ⋮ Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time ⋮ On levels in arrangements and Voronoi diagrams ⋮ The \(k\)-nearest-neighbor Voronoi diagram revisited ⋮ The power of geometric duality revisited ⋮ Visibility with a moving point of view ⋮ Computing Shapley values in the plane
This page was built for publication: Constructing Arrangements of Lines and Hyperplanes with Applications
