Constructing Arrangements of Lines and Hyperplanes with Applications

DOI10.1137/0215024zbMATH Open0603.68104DBLPjournals/siamcomp/EdelsbrunnerOS86OpenAlexW2120934134WikidataQ56442905 ScholiaQ56442905MaRDI QIDQ3740283FDOQ3740283

Authors: Joseph O'Rourke, Raimund Seidel, 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

Recommendations

• scientific article; zbMATH DE number 4032498
• scientific article; zbMATH DE number 4074477
• Constructing arrangements optimally in parallel
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• scientific article; zbMATH DE number 1182914

zbMATH Keywords

computational geometrycombinatorial geometryconfigurationsVoronoi diagramsoptimal algorithmgeometric transformationcell complex

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Polytopes and polyhedra (52Bxx) Polyhedra and polytopes; regular figures, division of spaces (51M20) Other problems of combinatorial convexity (52A37)

Cited In (only showing first 100 items - show all)

• A linear optimization oracle for zonotope computation
• New Complexity Bounds for Image Matching under Rotation and Scaling
• Geometric matching algorithms for two realistic terrains
• A theorem on the average number of subfaces in arrangements and oriented matroids
• Probing a set of hyperplanes by lines and related problems
• Capturing crossings: convex hulls of segment and plane intersections
• Optimal separable partitioning in the plane
• Computing nice projections of convex polyhedra
• Cutting hyperplane arrangements
• The number of edges of many faces in a line segment arrangement
• Output-sensitive cell enumeration in hyperplane arrangements
• TOPOLOGICAL PEELING AND APPLICATIONS
• Lower bounds on moving a ladder in two and three dimensions
• Line arrangements and range search
• Bounding the number of \(k\)-faces in arrangements of hyperplanes
• Shape Matching by Random Sampling
• INDUCING POLYGONS OF LINE ARRANGEMENTS
• On vertical ray shooting in arrangements
• Deciding robust feasibility and infeasibility using a set containment approach: an application to stationary passive gas network operations
• Identification of points using disks
• Stabbing information of a simple polygon
• The partition bargaining problem
• Finding points in general position
• Efficient algorithms for maximum regression depth
• Erased arrangements of linear and convex decompositions of polyhedra
• A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks
• Shadow-boundaries of convex bodies
• Illumination by floodlights
• Computing a sweeping-plane in regular (``general) position: A numerical and a symbolic solution
• A dual approach to detect polyhedral intersections in arbitrary dimensions
• Flip distance between triangulations of a simple polygon is NP-complete
• Subset selection in sparse matrices
• Algorithms for high dimensional stabbing problems
• WALKING IN AN ARRANGEMENT TOPOLOGICALLY
• An optimal algorithm for the boundary of a cell in a union of rays
• Polygonizations of point sets in the plane
• Counting convex \(k\)-gons in planar point sets
• Covering grids and orthogonal polygons with periscope guards
• Geometric medians
• Largest and smallest area triangles on imprecise points
• Robot motion planning and the single cell problem in arrangements
• Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
• On levels in arrangements and Voronoi diagrams
• On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space
• Parallel algorithms for arrangements
• A tail estimate for Mulmuley's segment intersection algorithm
• Edge-skeletons in arrangements with applications
• Recognising polytopical cell complexes and constructing projection polyhedra
• Reaching a goal with directional uncertainty
• Title not available (Why is that?)
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• All-maximum and all-minimum problems under some measures
• New complexity bounds for image matching under rotation and scaling
• Sorting weighted distances with applications to objective function evaluations in single facility location problems.
• Combinatorial face enumeration in arrangements and oriented matroids
• A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
• Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm
• Algorithms for marketing-mix optimization
• POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION
• A polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
• Selecting distances in arrangements of hyperplanes spanned by points.
• Peeling potatoes near-optimally in near-linear time
• A fast planar partition algorithm. I
• Approximation algorithms for free-label maximization
• A deterministic view of random sampling and its use in geometry
• The complexity of point configurations
• Representing geometric structures in \(d\) dimensions: Topology and order
• Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
• The use of edge-directions and linear programming to enumerate vertices
• The complexity of many cells in arrangements of planes and related problems
• Counting \(k\)-subsets and convex \(k\)-gons in the plane
• Searching for empty convex polygons
• On counting pairs of intersecting segments and off-line triangle range searching
• Voronoi diagrams and arrangements
• Finding constrained and weighted Voronoi diagrams in the plane
• Finding all pure strategy Nash equilibria in a planar location game
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Some results on point visibility graphs
• Combinatorial complexity bounds for arrangements of curves and spheres
• An approximation algorithm for least median of squares regression
• Algorithms for weak and wide separation of sets
• Computing optimal islands
• The power of geometric duality
• On the gap between the quadratic integer programming problem and its semidefinite relaxation
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• Halfspace range search: An algorithmic application of k-sets
• Point set pattern matching in \(d\)-dimensions
• Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
• Cutting hyperplanes for divide-and-conquer
• Implicitly representing arrangements of lines or segments
• The complexity and construction of many faces in arrangements of lines and of segments
• Shape matching by random sampling
• Better lower bounds on detecting affine and spherical degeneracies
• A new polynomially solvable class of quadratic optimization problems with box constraints
• Applications of random sampling in computational geometry. II
• New applications of random sampling in computational geometry
• The complexity of cells in three-dimensional arrangements
• Hamiltonicity and colorings of arrangement graphs
• Topologically sweeping an arrangement
• The farthest point Delaunay triangulation minimizes angles

This page was built for publication: Constructing Arrangements of Lines and Hyperplanes with Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740283)