Constructing Arrangements of Lines and Hyperplanes with Applications

DOI10.1137/0215024zbMath0603.68104OpenAlexW2120934134WikidataQ56442905 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

zbMATH Keywords

configurations combinatorial geometry optimal algorithm computational geometry Voronoi diagrams geometric transformation cell complex

Mathematics Subject Classification ID

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

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, Ray shooting on triangles in 3-space, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, Output-sensitive cell enumeration in hyperplane arrangements, Approximating finite weighted point sets by hyperplanes, Convex polygons made from few lines and convex decompositions of polyhedra, Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining, Corrigendum: Topologically sweeping an arrangement, Triangles in space or building (and analyzing) castles in the air, A fast planar partition algorithm. I, An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings, TOPOLOGICAL PEELING AND APPLICATIONS, A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks, Peeling Potatoes Near-Optimally in Near-Linear Time, Maintaining proximity in higher dimensional spaces, Complexity of training ReLU neural network, On rainbow quadrilaterals in colored point sets, Two-Dimensional Pattern Matching with Combined Scaling and Rotation, Unnamed Item, Solving some vector subset problems by Voronoi diagrams, Sparse PCA on fixed-rank matrices, On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space, Approximating length-restricted means under dynamic time warping, Reporting the crossing-free segments of a complete geometric graph, Finding Points in General Position, A New Algorithm for Enumeration of Cells of Hyperplane Arrangements and a Comparison with Avis and Fukuda's Reverse Search, An exact algorithm for finding a vector subset with the longest sum, Deciding Robust Feasibility and Infeasibility Using a Set Containment Approach: An Application to Stationary Passive Gas Network Operations, Minimal Representations of Order Types by Geometric Graphs, COMPUTING NICE PROJECTIONS OF CONVEX POLYHEDRA, The use of edge-directions and linear programming to enumerate vertices, A new duality result concerning Voronoi diagrams, The partition bargaining problem, PROPERTIES OF ARRANGEMENT GRAPHS, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Computing unique three-dimensional object aspects representation, Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations, POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION, Shape Matching by Random Sampling, Spanning trees with low crossing number, A tail estimate for Mulmuley's segment intersection algorithm, Complexity and algorithms for finding a subset of vectors with the longest sum, Subset Selection in Sparse Matrices, Unnamed Item, New Complexity Bounds for Image Matching under Rotation and Scaling, Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy