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)
68Q25: Analysis of algorithms and problem complexity
Related Items
COMPUTING CLOSEST POINTS FOR SEGMENTS, Ray shooting and intersection searching amidst fat convex polyhedra in 3-space, Local polyhedra and geometric graphs, On counting point-hyperplane incidences, Lower bounds for off-line range searching, 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
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
