Stabbing line segments

DOI10.1007/BF01934440zbMath0484.68053OpenAlexW1965327420WikidataQ54310067 ScholiaQ54310067MaRDI QIDQ1163869

Arnold L. Rosenberg, Hermann Maurer, Franco P. Preparata, Ermo Welzl, Herbert Edelsbrunner, Derick Wood

Publication date: 1982

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01934440

zbMATH Keywords

algorithmdata structurescomputational geometrydivide-and-conquergeometric transformdynamization22, 274-281 (1982)plane-sweep

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (39)

Sets of lines and cutting out polyhedral objects ⋮ Diameter partitioning ⋮ The complexity of cells in three-dimensional arrangements ⋮ Finding transversals for sets of simple geometric figures ⋮ Ray shooting on triangles in 3-space ⋮ Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications ⋮ Geometric clustering in normed planes ⋮ Separating translates in the plane: Combinatorial bounds and an algorithm ⋮ Farthest line segment Voronoi diagrams ⋮ On intersecting a set of parallel line segments with a convex polygon of minimum area ⋮ Sweep methods for parallel computational geometry ⋮ ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM ⋮ Discrete and mixed two-center problems for line segments ⋮ Algorithms for high dimensional stabbing problems ⋮ The upper envelope of piecewise linear functions: Algorithms and applications ⋮ Linear approximation of simple objects ⋮ Ordered stabbing of pairwise disjoint convex sets in linear time ⋮ A role of lower semicontinuous functions in the combinatorial complexity of geometric problems ⋮ Linear approximation of simple objects ⋮ Stabbing segments with rectilinear objects ⋮ A convex hull algorithm for discs, and applications ⋮ Stabbing circles for sets of segments in the plane ⋮ Geometric orderings of intersecting translates and their applications ⋮ Algorithms for weak and wide separation of sets ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ Stabbers of line segments in the plane ⋮ Some clustering algorithms in normed planes ⋮ Linear approximation of simple objects ⋮ Maximum spanning trees in normed planes ⋮ The maximum number of ways to stab n convex nonintersecting sets in the plane is 2n-2 ⋮ Computing shortest transversals ⋮ Polyhedral line transversals in space ⋮ Geometry of the Gass-Saaty parametric cost LP algorithm ⋮ ON INTERSECTING A SET OF ISOTHETIC LINE SEGMENTS WITH A CONVEX POLYGON OF MINIMUM AREA ⋮ Efficient algorithm for transversal of disjoint convex polygons. ⋮ Transversal of disjoint convex polygons. ⋮ On the maximal number of edges of many faces in an arrangement ⋮ The one-dimensional weighted Voronoi diagram ⋮ The higher-order Voronoi diagram of line segments

Cites Work

• Polygonal intersection searching
• Dynamization of order decomposable set problems

This page was built for publication: Stabbing line segments