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
