On the union of fat wedges and separating a collection of segments by a line

DOI10.1016/0925-7721(93)90018-2zbMath0801.68167OpenAlexW2054236013MaRDI QIDQ1314526

Alon Efrat, Günter Rote, Micha Sharir

Publication date: 29 November 1994

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(93)90018-2

zbMATH Keywords

visibility graphfat trianglesseparator line

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (17)

Shattering a set of objects in 2D ⋮ On the union complexity of families of axis-parallel rectangles with a low packing number ⋮ Approximate unions of lines and Minkowski sums ⋮ Separating and shattering long line segments ⋮ Computing depth orders and related problems ⋮ LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS ⋮ Range searching in low-density environments ⋮ On a class of \(O(n^ 2)\) problems in computational geometry ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Computing depth orders for fat objects and related problems ⋮ On fat partitioning, fat covering and the union size of polygons ⋮ Linear size binary space partitions for fat objects ⋮ On a class of \(O(n^2)\) problems in computational geometry ⋮ Piercing pairwise intersecting convex shapes in the plane ⋮ Decomposition of Multiple Packings with Subquadratic Union Complexity ⋮ SKIP QUADTREES: DYNAMIC DATA STRUCTURES FOR MULTIDIMENSIONAL POINT SETS ⋮ Improved bounds on the union complexity of fat objects

Cites Work

• Unnamed Item
• Finding the upper envelope of n line segments in O(n log n) time
• The complexity and construction of many faces in arrangements of lines and of segments
• An optimal algorithm for the boundary of a cell in a union of rays
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Topologically sweeping an arrangement
• Better lower bounds on detecting affine and spherical degeneracies
• Applications of random sampling in computational geometry. II
• A fast planar partition algorithm. I
• An Output-Sensitive Algorithm for Computing Visibility Graphs
• Fat Triangles Determine Linearly Many Holes
• An optimal algorithm for intersecting line segments in the plane

This page was built for publication: On the union of fat wedges and separating a collection of segments by a line