Topologically sweeping an arrangement

DOI10.1016/0022-0000(89)90038-XzbMATH Open0676.68013OpenAlexW4213074663WikidataQ56442903 ScholiaQ56442903MaRDI QIDQ1122981FDOQ1122981

Authors: Herbert Edelsbrunner, Leonidas Guibas 

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

Recommendations

• Line arrangements and range search
• WALKING IN AN ARRANGEMENT TOPOLOGICALLY
• Space-efficient plane-sweep algorithms
• scientific article; zbMATH DE number 4060713
• scientific article; zbMATH DE number 49092

zbMATH Keywords

computational geometryline arrangementstopological sweepamortized complexity analysisduality transformsweepline paradigm

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The power of geometric duality
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Konvexe Fünfecke in ebenen Punktmengen
• Title not available (Why is that?)
• Sets with No Empty Convex 7-Gons
• Optimal Point Location in a Monotone Subdivision
• Decomposable searching problems I. Static-to-dynamic transformation
• Euclidean shortest paths in the presence of rectilinear barriers
• Plane-sweep algorithms for intersecting geometric figures
• Title not available (Why is that?)
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
• How good is the information theory bound in sorting?
• Amortized Computational Complexity
• Constructing Belts in Two-Dimensional Arrangements with Applications
• Title not available (Why is that?)

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

• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• On triangulating three-dimensional polygons
• All-maximum and all-minimum problems under some measures
• The exact fitting problem in higher dimensions
• Submodular function minimization
• Polygon nesting and robustness
• Visibility graphs and obstacle-avoiding shortest paths
• TOPOLOGICAL PEELING AND APPLICATIONS
• Sweeping points
• Line arrangements and range search
• Bottleneck partial-matching Voronoi diagrams and applications
• On a class of \(O(n^2)\) problems in computational geometry
• Space-efficient plane-sweep algorithms
• Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step
• On the least trimmed squares estimator
• Taking a walk in a planar arrangement
• Combinatorial polar orderings and recursively orderable arrangements
• Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
• Title not available (Why is that?)
• Searching for empty convex polygons
• Pattern matching in a digitized image
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• Combinatorial complexity bounds for arrangements of curves and spheres
• Title not available (Why is that?)
• A practical approximation algorithm for the LMS line estimator
• Separating and shattering long line segments
• A unified scheme for detecting fundamental curves in binary edge images
• Implicitly representing arrangements of lines or segments
• Better lower bounds on detecting affine and spherical degeneracies
• Topologically sweeping visibility complexes via pseudotriangulations
• On a class of \(O(n^ 2)\) problems in computational geometry
• EXACT ALGORITHMS FOR CIRCLES ON THE SPHERE
• Infimaximal Frames: A Technique for Making Lines Look Like Segments
• Scanline algorithms on a grid
• The maximin line problem with regional demand
• The complexity of cutting complexes
• Monotone paths in line arrangements
• On the general motion-planning problem with two degrees of freedom
• Shattering a set of objects in 2D
• Computing convolutions by reciprocal search
• Illumination by floodlights
• Computational geometric approach to submodular function minimization for multiclass queueing systems
• On the union of fat wedges and separating a collection of segments by a line
• Optimal and suboptimal robust algorithms for proximity graphs
• Iterated nearest neighbors and finding minimal polytopes
• Computing a sweeping-plane in regular (``general) position: A numerical and a symbolic solution
• Space sweep solves intersection of convex polyhedra
• Relative convex hulls in semi-dynamic arrangements
• On some monotone path problems in line arrangements
• Corrigendum: Topologically sweeping an arrangement
• Empty pseudo-triangles in point sets
• WALKING IN AN ARRANGEMENT TOPOLOGICALLY
• Minimal tangent visibility graphs
• Sweeps, arrangements and signotopes
• Constructing Belts in Two-Dimensional Arrangements with Applications
• Median hyperplanes in normed spaces -- a survey
• MINIMUM SEPARATION IN WEIGHTED SUBDIVISIONS
• On 2D constrained discrete rigid transformations
• Algorithms for bivariate medians and a Fermat-Torricelli problem for lines.
• Title not available (Why is that?)
• On Combinatorial Depth Measures
• Largest and smallest area triangles on imprecise points
• Locating an obnoxious plane
• Finding minimum area \(k\)-gons
• Title not available (Why is that?)
• Counting convex polygons in planar point sets
• Verifiable implementations of geometric algorithms using finite precision arithmetic
• Rounding Arrangements Dynamically
• LR characterization of chirotopes of finite planar families of pairwise disjoint convex bodies
• Connected Rectilinear Graphs on Point Sets
• Partitioning arrangements of lines. II: Applications
• Algorithms for deciding the containment of polygons
• Computing pseudotriangulations via branched coverings
• Sorting jordan sequences in linear time using level-linked search trees
• Efficient algorithms and implementations for optimizing the sum of linear fractional functions, with applications
• The parameterized complexity of finding point sets with hereditary properties
• Complexity of computing interval matrix powers for special classes of matrices.
• FINDING POPULAR PLACES
• A topology construction from line drawings using a uniform plane subdivision technique.
• Output-sensitive cell enumeration in hyperplane arrangements
• Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra
• Constructing arrangements optimally in parallel
• On some geometric optimization problems in layered manufacturing
• Finding Popular Places
• Regular systems of paths and families of convex sets in convex position
• Finding minimum area simple pentagons
• Algorithms for colourful simplicial depth and medians in the plane
• The effect of planarization on width
• Computing colourful simplicial depth and Median in \(\mathbb{R}_2\)
• On the complexity of the \(k\)-level in arrangements of pseudoplanes
• Title not available (Why is that?)
• Asymptotic speed-ups in constructive solid geometry
• Sweep methods for parallel computational geometry
• MAINTAINING VISIBILITY INFORMATION OF PLANAR POINT SETS WITH A MOVING VIEWPOINT
• AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE
• Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees
• THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS
• Kernelization of the subset general position problem in geometry
• A sweep-line algorithm for the inclusion hierarchy among circles
• Sweeping Points

This page was built for publication: Topologically sweeping an arrangement

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