Algorithms for bichromatic line-segment problems and polyhedral terrains
From MaRDI portal
Publication:1314429
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)
Related Items
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
