Constructing Arrangements of Lines and Hyperplanes with Applications
From MaRDI portal
Publication:3740283
DOI10.1137/0215024zbMath0603.68104WikidataQ56442905 ScholiaQ56442905MaRDI QIDQ3740283
Joseph O'Rourke, Herbert Edelsbrunner, Raimund Seidel
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
configurations; combinatorial geometry; optimal algorithm; computational geometry; Voronoi diagrams; geometric transformation; cell complex
68Q25: Analysis of algorithms and problem complexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
51M20: Polyhedra and polytopes; regular figures, division of spaces
52A37: Other problems of combinatorial convexity
52Bxx: Polytopes and polyhedra
Related Items
Reporting the crossing-free segments of a complete geometric graph, PROPERTIES OF ARRANGEMENT GRAPHS, POINT AND LINE SEGMENT RECONSTRUCTION FROM VISIBILITY INFORMATION, TOPOLOGICAL PEELING AND APPLICATIONS, A new duality result concerning Voronoi diagrams, Computing unique three-dimensional object aspects representation, 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, Algorithms for deciding the containment of polygons, Reaching a goal with directional uncertainty, On counting pairs of intersecting segments and off-line triangle range searching, A theorem on the average number of subfaces in arrangements and oriented matroids, Algorithms for weak and wide separation of sets, 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, On levels in arrangements and Voronoi diagrams, Hamiltonicity and colorings of arrangement graphs, An optimal algorithm for the boundary of a cell in a union of rays, Searching for empty convex polygons, Triangulating a nonconvex polytope, Algorithms for high dimensional stabbing problems, Combinatorial complexity bounds for arrangements of curves and spheres, Partitioning arrangements of lines. II: Applications, New bounds on the unconstrained quadratic integer programming problem, Efficient algorithms for maximum regression depth, Topological sweep of the complete graph, Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time, The power of geometric duality revisited, Halfspace range search: An algorithmic application of k-sets, The complexity of cells in three-dimensional arrangements, Voronoi diagrams and arrangements, Visibility of disjoint polygons, Edge-skeletons in arrangements with applications, Polygonizations of point sets in the plane, Recognising polytopical cell complexes and constructing projection polyhedra, Lower bounds on moving a ladder in two and three dimensions, Verifiable implementations of geometric algorithms using finite precision arithmetic, Topologically sweeping an arrangement, Bounding the number of \(k\)-faces in arrangements of hyperplanes, The complexity of point configurations, Cutting hyperplane arrangements, Counting \(k\)-subsets and convex \(k\)-gons in the plane, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Finding minimum area \(k\)-gons, The farthest point Delaunay triangulation minimizes angles, Counting convex \(k\)-gons in planar point sets, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, The number of edges of many faces in a line segment arrangement, Geometric medians, Implicitly representing arrangements of lines or segments, Median hyperplanes in normed spaces -- a survey, Stabbing information of a simple polygon, Visibility with a moving point of view, Iterated nearest neighbors and finding minimal polytopes, Better lower bounds on detecting affine and spherical degeneracies, Erased arrangements of linear and convex decompositions of polyhedra, Illumination by floodlights, Finding constrained and weighted Voronoi diagrams in the plane, Sorting weighted distances with applications to objective function evaluations in single facility location problems., Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm, Constructing arrangements optimally in parallel, Representing geometric structures in \(d\) dimensions: Topology and order, New applications of random sampling in computational geometry, Applications of random sampling in computational geometry. II, Robot motion planning and the single cell problem in arrangements, Point set pattern matching in \(d\)-dimensions, Optimal separable partitioning in the plane, Parallel algorithms for arrangements, Computing half-plane and strip discrepancy of planar point sets, Point location in zones of \(k\)-flats in arrangements, Shadow-boundaries of convex bodies, Covering grids and orthogonal polygons with periscope guards, A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis, Ray shooting on triangles in 3-space, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, The use of edge-directions and linear programming to enumerate vertices, The partition bargaining problem, On the gap between the quadratic integer programming problem and its semidefinite relaxation, Corrigendum: Topologically sweeping an arrangement, Triangles in space or building (and analyzing) castles in the air, A fast planar partition algorithm. I, Spanning trees with low crossing number, Two-Dimensional Pattern Matching with Combined Scaling and Rotation, On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space, Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations, Shape Matching by Random Sampling, New Complexity Bounds for Image Matching under Rotation and Scaling
