Algorithms for bichromatic line-segment problems and polyhedral terrains

DOI10.1007/BF01182771zbMath0818.68140MaRDI QIDQ1314429

Herbert Edelsbrunner, Bernard Chazelle, Leonidas J. Guibas, Micha Sharir

Publication date: 20 August 1995

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmspolyhedral terrainsline-segment intersection

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (28)

Sets of lines and cutting out polyhedral objects ⋮ On lines missing polyhedral sets in 3-space ⋮ Finding a largest-area triangle in a terrain in near-linear time ⋮ Can visibility graphs be represented compactly? ⋮ Approximate unions of lines and Minkowski sums ⋮ Finding Pairwise Intersections Inside a Query Range ⋮ Computing depth orders for fat objects and related problems ⋮ Bipartite diameter and other measures under translation ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Partitioning arrangements of lines. II: Applications ⋮ Multidimensional segment trees can do range updates in poly-logarithmic time ⋮ Data structures for extension violations in a query range ⋮ External-memory algorithms for processing line segments in geographic information systems ⋮ On counting pairs of intersecting segments and off-line triangle range searching ⋮ Counting and cutting cycles of lines and rods in space ⋮ On the number of regular vertices of the union of Jordan regions ⋮ Diameter, width, closest line pair, and parametric searching ⋮ On the number of regular vertices of the union of Jordan regions ⋮ Local polyhedra and geometric graphs ⋮ Unnamed Item ⋮ Placing Text Boxes on Graphs ⋮ Region-restricted clustering for geographic data mining ⋮ Computing the Distance between Piecewise-Linear Bivariate Functions ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model ⋮ OPTIMAL FACILITY LOCATION UNDER VARIOUS DISTANCE FUNCTIONS ⋮ Reporting intersecting pairs of convex polytopes in two and three dimensions ⋮ On constant factors in comparison-based geometric algorithms and data structures

Cites Work

• Unnamed Item
• Unnamed Item
• Computing convolutions by reciprocal search
• Fractional cascading. I: A data structuring technique
• The shortest watchtower and related problems for polyhedral terrains
• Cutting hyperplanes for divide-and-conquer
• Reporting and counting segment intersections
• Lines in space: Combinatorics and algorithms
• An algorithm for generalized point location and its applications
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Optimal Point Location in a Monotone Subdivision
• An Optimal-Time Algorithm for Slope Selection
• Rectilinear line segment intersection, layered segment trees, and dynamization
• An optimal algorithm for intersecting line segments in the plane

This page was built for publication: Algorithms for bichromatic line-segment problems and polyhedral terrains