Topologically sweeping an arrangement

DOI10.1016/0022-0000(89)90038-XzbMath0676.68013OpenAlexW4213074663WikidataQ56442903 ScholiaQ56442903MaRDI QIDQ1122981

Leonidas J. Guibas, Herbert Edelsbrunner

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90038-x

zbMATH Keywords

computational geometry line arrangements topological sweep amortized complexity analysis duality transform sweepline paradigm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items

Shattering a set of objects in 2D, Optimal and suboptimal robust algorithms for proximity graphs, Iterated nearest neighbors and finding minimal polytopes, Separability of imprecise points, Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications, Pattern matching in a digitized image, Separating and shattering long line segments, Computing colourful simplicial depth and Median in \(\mathbb{R}_2\), Finding degeneracies among sets of lines, Computing convolutions by reciprocal search, Better lower bounds on detecting affine and spherical degeneracies, Output-sensitive cell enumeration in hyperplane arrangements, Approximating finite weighted point sets by hyperplanes, Asymptotic speed-ups in constructive solid geometry, Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining, Combinatorial polar orderings and recursively orderable arrangements, Counting convex polygons in planar point sets, A linear-time algorithm for constructing a circular visibility diagram, Corrigendum: Topologically sweeping an arrangement, FINDING POPULAR PLACES, On some monotone path problems in line arrangements, On a class of \(O(n^ 2)\) problems in computational geometry, TOPOLOGICAL PEELING AND APPLICATIONS, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, The complexity of cutting complexes, Verifiable implementations of geometric algorithms using finite precision arithmetic, The maximin line problem with regional demand, The exact fitting problem in higher dimensions, LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies, Minimal tangent visibility graphs, Computational geometric approach to submodular function minimization for multiclass queueing systems, Illumination by floodlights, All-maximum and all-minimum problems under some measures, On triangulating three-dimensional polygons, On rainbow quadrilaterals in colored point sets, Algorithms for bivariate medians and a Fermat-Torricelli problem for lines., Algorithms for Colourful Simplicial Depth and Medians in the Plane, On a class of \(O(n^2)\) problems in computational geometry, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set, Bottleneck partial-matching Voronoi diagrams and applications, Ham-sandwich cuts for abstract order types, Bottleneck convex subsets: finding \(k\) large convex sets in a point set, Searching for empty convex polygons, Combinatorial complexity bounds for arrangements of curves and spheres, Polygon nesting and robustness, Complexity of computing interval matrix powers for special classes of matrices., Partitioning arrangements of lines. II: Applications, The Effect of Planarization on Width, MAINTAINING VISIBILITY INFORMATION OF PLANAR POINT SETS WITH A MOVING VIEWPOINT, Visibility graphs and obstacle-avoiding shortest paths, On the least trimmed squares estimator, Finding Popular Places, Relative convex hulls in semi-dynamic arrangements, On Combinatorial Depth Measures, On disjoint concave chains in arrangements of (pseudo) lines, Linear approximation of simple objects, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Finding minimum area \(k\)-gons, Algorithms for deciding the containment of polygons, On 2D constrained discrete rigid transformations, Largest and smallest area triangles on imprecise points, The Parameterized Complexity of Finding Point Sets with Hereditary Properties, THE ONION DIAGRAM: A VORONOI-LIKE TESSELLATION OF A PLANAR LINE SPACE AND ITS APPLICATIONS, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra, A Practical, Globally Optimal Algorithm for Geometric Matching under Uncertainty, A unified scheme for detecting fundamental curves in binary edge images, Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications, Locating an obnoxious plane, Computing pseudotriangulations via branched coverings, On the complexity of the \(k\)-level in arrangements of pseudoplanes, Unnamed Item, EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE, THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS, Regular systems of paths and families of convex sets in convex position, ON COMPUTING TRANSLATIONAL SWEPT VOLUMES, Submodular function minimization, The Effect of Planarization on Width, Connected Rectilinear Graphs on Point Sets, Linear approximation of simple objects, Constructing arrangements optimally in parallel, Unnamed Item, MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS, On the general motion-planning problem with two degrees of freedom, Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra, Implicitly representing arrangements of lines or segments, Finding minimum area simple pentagons, A practical approximation algorithm for the LMS line estimator, Convex polygons in Cartesian products, Topologically sweeping visibility complexes via pseudotriangulations, On some geometric optimization problems in layered manufacturing, Empty pseudo-triangles in point sets, Median hyperplanes in normed spaces -- a survey, Gathering by Repulsion., On the union of fat wedges and separating a collection of segments by a line, Monotone paths in line arrangements

Cites Work