Recommendations
Cites work
- A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons
- Better lower bounds on detecting affine and spherical degeneracies
- Can visibility graphs be represented compactly?
- Combinatorial complexity bounds for arrangements of curves and spheres
- Computing and Verifying Depth Orders
- Covering of graphs by complete bipartite subgraphs; complexity of 0-1 matrices
- Cutting hyperplanes for divide-and-conquer
- CUTTINGS AND APPLICATIONS
- Diameter, width, closest line pair, and parametric searching
- Extremal problems in discrete geometry
- How hard is half-space range searching?
- scientific article; zbMATH DE number 3841905 (Why is no real title available?)
- scientific article; zbMATH DE number 4213491 (Why is no real title available?)
- scientific article; zbMATH DE number 4032498 (Why is no real title available?)
- scientific article; zbMATH DE number 51258 (Why is no real title available?)
- scientific article; zbMATH DE number 3613058 (Why is no real title available?)
- scientific article; zbMATH DE number 1263252 (Why is no real title available?)
- scientific article; zbMATH DE number 3893918 (Why is no real title available?)
- scientific article; zbMATH DE number 4197419 (Why is no real title available?)
- Implicitly representing arrangements of lines or segments
- Lower bounds for algebraic decision trees
- Lower Bounds on the Complexity of Polytope Range Searching
- Lower Bounds on the Complexity of Some Optimal Data Structures
- On k-Hulls and Related Problems
- On ray shooting in convex polytopes
- On Sets of Distances of n Points
- Partitioning arrangements of lines. II: Applications
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Range searching with efficient hierarchical cuttings
- Reporting and counting segment intersections
- Simplex range reporting on a pointer machine
- 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
Cited in
(37)- Better lower bounds on detecting affine and spherical degeneracies
- Covering lattice points by subspaces and counting point-hyperplane incidences
- Local polyhedra and geometric graphs
- On counting point-hyperplane incidences
- Lower bounds for off-line range searching
- Subquadratic algorithms for algebraic 3SUM
- 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
- scientific article; zbMATH DE number 4151859 (Why is no real title available?)
- scientific article; zbMATH DE number 4011939 (Why is no real title available?)
- Space-Time Tradeoffs for Emptiness Queries
- An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
- Simplex Range Searching and Its Variants: A Review
- scientific article; zbMATH DE number 3997167 (Why is no real title available?)
- scientific article; zbMATH DE number 4114000 (Why is no real title available?)
- COMPUTING CLOSEST POINTS FOR SEGMENTS
- Output sensitive algorithms for approximate incidences and their applications
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Finding orthogonal vectors in discrete structures
- Approximating Minimization Diagrams and Generalized Proximity Search
- Jaywalking your dog: computing the Fréchet distance with shortcuts
- scientific article; zbMATH DE number 7662166 (Why is no real title available?)
- Some geometric lower bounds
- Bold graph drawings
- Algorithms for computing closest points for segments
- Algorithms for halfplane coverage and related problems
- Algorithms for computing closest points for segments
- Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
- On the number of incidences when avoiding an induced biclique in geometric settings
- Quantum algorithms for Hopcroft's problem
- Segment proximity graphs and nearest neighbor queries amid disjoint segments
- Algorithms for halfplane coverage and related problems
- Segment proximity graphs and nearest neighbor queries amid disjoint segments
- Compact representation of semilinear and terrain-like graphs
- An O(n n) algorithm for single-source shortest paths in disk graphs
- Reverse shortest path problem for unit-disk graphs
- Ray shooting and intersection searching amidst fat convex polyhedra in 3-space
This page was built for publication: New lower bounds for Hopcroft's problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1816464)
