New lower bounds for Hopcroft's problem
From MaRDI portal
Publication:1816464
DOI10.1007/BF02712875zbMath0857.68061MaRDI QIDQ1816464
Publication date: 3 March 1997
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Related Items
On counting point-hyperplane incidences ⋮ Lower bounds for off-line range searching ⋮ Reverse shortest path problem for unit-disk graphs ⋮ COMPUTING CLOSEST POINTS FOR SEGMENTS ⋮ An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Unnamed Item ⋮ Covering lattice points by subspaces and counting point-hyperplane incidences ⋮ Bold graph drawings ⋮ Ray shooting and intersection searching amidst fat convex polyhedra in 3-space ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D ⋮ Local polyhedra and geometric graphs ⋮ Unnamed Item ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Approximating Minimization Diagrams and Generalized Proximity Search ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity and construction of many faces in arrangements of lines and of segments
- The complexity of many cells in arrangements of planes and related problems
- How hard is half-space range searching?
- Range searching with efficient hierarchical cuttings
- Diameter, width, closest line pair, and parametric searching
- On ray shooting in convex polytopes
- Extremal problems in discrete geometry
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- Combinatorial complexity bounds for arrangements of curves and spheres
- Partitioning arrangements of lines. II: Applications
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Implicitly representing arrangements of lines or segments
- Can visibility graphs be represented compactly?
- Better lower bounds on detecting affine and spherical degeneracies
- Reporting and counting segment intersections
- Simplex range reporting on a pointer machine
- Lower Bounds on the Complexity of Polytope Range Searching
- On k-Hulls and Related Problems
- Lower Bounds on the Complexity of Some Optimal Data Structures
- Lower bounds for algebraic decision trees
- Computing and Verifying Depth Orders
- CUTTINGS AND APPLICATIONS
- On Sets of Distances of n Points
