On the public citation graph

New lower bounds for Hopcroft's problem

0 signed · 94 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-52921-7_91openalex-snapshot

A hyperplane Incidence problem with applications to counting distances

inferredcites →https://doi.org/10.1007/978-3-0348-5438-2_10openalex-snapshot

On the decomposition of graphs into complete bipartite subgraphs

inferredcites →https://doi.org/10.1007/978-3-642-61568-9openalex-snapshot

Algorithms in Combinatorial Geometry

inferredcites →https://doi.org/10.1007/bf01758854openalex-snapshot

Quasi-optimal upper bounds for simplex range searching and new zone theorems

inferredcites →https://doi.org/10.1007/bf02187742openalex-snapshot

Implicitly representing arrangements of lines or segments

inferredcites →https://doi.org/10.1007/bf02187783openalex-snapshot

Combinatorial complexity bounds for arrangements of curves and spheres

inferredcites →https://doi.org/10.1007/bf02187784openalex-snapshot

The complexity and construction of many faces in arrangements of lines and of segments

inferredcites →https://doi.org/10.1007/bf02187785openalex-snapshot

The complexity of many cells in arrangements of planes and related problems

inferredcites →https://doi.org/10.1007/bf02187809openalex-snapshot

Partitioning arrangements of lines II: Applications

inferredcites →https://doi.org/10.1007/bf02189314openalex-snapshot

Cutting hyperplanes for divide-and-conquer

inferredcites →https://doi.org/10.1007/bf02573971openalex-snapshot

How hard is half-space range searching?

inferredcites →https://doi.org/10.1007/bf02573972openalex-snapshot

Range searching with efficient hierarchical cuttings

inferredcites →https://doi.org/10.1007/bf02573973openalex-snapshot

Diameter, width, closest line pair, and parametric searching

inferredcites →https://doi.org/10.1007/bf02573975openalex-snapshot

On ray shooting in convex polytopes

inferredcites →https://doi.org/10.1007/bf02579163openalex-snapshot

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

inferredcites →https://doi.org/10.1007/bf02579194openalex-snapshot

Extremal problems in discrete geometry

inferredcites →https://doi.org/10.1016/0022-0000(86)90025-5openalex-snapshot

Reporting and counting segment intersections

inferredcites →https://doi.org/10.1016/0196-6774(82)90002-5openalex-snapshot

Lower bounds for algebraic decision trees

inferredcites →https://doi.org/10.1016/0925-7721(91)90012-4openalex-snapshot

A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

inferredcites →https://doi.org/10.1016/0925-7721(95)00002-xopenalex-snapshot

Simplex range reporting on a pointer machine

inferredcites →https://doi.org/10.1016/c2013-0-11551-6openalex-snapshot

Oriented Projective Geometry

inferredcites →https://doi.org/10.1016/j.comgeo.2010.03.003openalex-snapshot

Reprint of: A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons

inferredcites →https://doi.org/10.1080/00029890.1946.11991674openalex-snapshot

On Sets of Distances of n Points

inferredcites →https://doi.org/10.1080/00029890.1970.11992573openalex-snapshot

On Sets of Distances of n Points

inferredcites →https://doi.org/10.1090/dimacs/004/18openalex-snapshot

A hyperplane incidence problem with applications to counting distances

inferredcites →https://doi.org/10.1090/s0894-0347-1989-1001852-0openalex-snapshot

Lower Bounds on the Complexity of Polytope Range Searching

inferredcites →https://doi.org/10.1109/sfcs.1993.366834openalex-snapshot

Better lower bounds on detecting affine and spherical degeneracies

inferredcites →https://doi.org/10.1126/science.56.1450.401openalex-snapshot

The Theory of Numbers

inferredcites →https://doi.org/10.1137/0210001openalex-snapshot

Lower Bounds on the Complexity of Some Optimal Data Structures

inferredcites →https://doi.org/10.1137/0216005openalex-snapshot

On k -Hulls and Related Problems

inferredcites →https://doi.org/10.1142/s0218195995000210openalex-snapshot

CUTTINGS AND APPLICATIONS

inferredcites →https://doi.org/10.1145/142675.142703openalex-snapshot

Incidence and nearest-neighbor problems for lines in 3-space

inferredcites →https://doi.org/10.1145/142675.142708openalex-snapshot

Computing and verifying depth orders

inferredcites →https://doi.org/10.1145/160985.161137openalex-snapshot

An expander-based approach to geometric optimization

inferredcites →https://doi.org/10.1145/160985.161160openalex-snapshot

Can visibility graphs be represented compactly?

inferredcites →https://doi.org/10.1145/225058.225291openalex-snapshot

Lower bounds for off-line range searching

inferredcites →https://doi.org/10.1145/800061.808735openalex-snapshot

Lower bounds for algebraic computation trees

inferredcites →https://doi.org/10.2307/2325168openalex-snapshot

Algorithms in Combinatorial Geometry.

inferredcites →https://doi.org/10.5860/choice.29-3952openalex-snapshot

Oriented projective geometry: a framework for geometric computations

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/0-387-25036-0_11openalex-snapshot

Incidences

inferred← citeshttps://doi.org/10.1007/0-387-29929-7_8openalex-snapshot

Incidence and Arrangement Problems

inferred← citeshttps://doi.org/10.1007/11682462_44openalex-snapshot

Lower Bounds for Geometric Diameter Problems

inferred← citeshttps://doi.org/10.1007/978-0-387-87363-3_2openalex-snapshot

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles

inferred← citeshttps://doi.org/10.1007/978-3-030-83508-8_47openalex-snapshot

Reverse Shortest Path Problem for Unit-Disk Graphs

inferred← citeshttps://doi.org/10.1007/978-3-319-44479-6_1openalex-snapshot

Simplex Range Searching and Its Variants: A Review

inferred← citeshttps://doi.org/10.1007/s00453-002-0967-4openalex-snapshot

Reporting Red--Blue Intersections between Two Sets of Connected Line Segments

inferred← citeshttps://doi.org/10.1007/s00453-007-9010-0openalex-snapshot

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

inferred← citeshttps://doi.org/10.1007/s00453-026-01395-3openalex-snapshot

Segment Proximity Graphs and Nearest Neighbor Queries amid Disjoint Segments

inferred← citeshttps://doi.org/10.1007/s00454-003-2856-2openalex-snapshot

On the Complexity of Halfspace Area Queries

inferred← citeshttps://doi.org/10.1007/s00454-003-2949-yopenalex-snapshot

Testing Homotopy for Paths in the Plane

inferred← citeshttps://doi.org/10.1007/s00454-007-9019-9openalex-snapshot

Computing the Detour and Spanning Ratio of Paths, Trees, and Cycles in 2D and 3D

inferred← citeshttps://doi.org/10.1007/s00454-018-0040-yopenalex-snapshot

Subquadratic Algorithms for Algebraic 3SUM

inferred← citeshttps://doi.org/10.1007/s00454-018-9970-7openalex-snapshot

Covering Lattice Points by Subspaces and Counting Point–Hyperplane Incidences

inferred← citeshttps://doi.org/10.1007/s00454-024-00648-8openalex-snapshot

On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings

inferred← citeshttps://doi.org/10.1007/s00454-024-00709-yopenalex-snapshot

Algorithms for Halfplane Coverage and Related Problems

inferred← citeshttps://doi.org/10.1016/b978-044482537-7/50003-6openalex-snapshot

Arrangements and Their Applications**Work by PA. was supported by Army Research Office MURI grant DAAH04-96-1-0013, by a Sloan fellowship, by an NYI award, and by a grant from the U.S.–Israeli Binational Science Foundation. Work by M.S. was supported by NSF Grants CCR-91-22103 and CCR-93-11127, by…

inferred← citeshttps://doi.org/10.1016/j.comgeo.2004.08.004openalex-snapshot

Local polyhedra and geometric graphs

inferred← citeshttps://doi.org/10.1016/j.comgeo.2007.10.006openalex-snapshot

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

inferred← citeshttps://doi.org/10.1016/j.comgeo.2011.06.002openalex-snapshot

Bold graph drawings

inferred← citeshttps://doi.org/10.1016/j.comgeo.2025.102196openalex-snapshot

Algorithms for computing closest points for segments

inferred← citeshttps://doi.org/10.1016/j.entcs.2016.03.005openalex-snapshot

Into the Square: On the Complexity of Some Quadratic-time Solvable Problems

inferred← citeshttps://doi.org/10.1016/j.jda.2003.12.001openalex-snapshot

Selecting distances in arrangements of hyperplanes spanned by points

inferred← citeshttps://doi.org/10.1016/s0925-7721(02)00127-xopenalex-snapshot

On counting point-hyperplane incidences

inferred← citeshttps://doi.org/10.1016/s0925-7721(99)00055-3openalex-snapshot

Queries with segments in Voronoi diagrams

inferred← citeshttps://doi.org/10.1090/bull/1653openalex-snapshot

The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

inferred← citeshttps://doi.org/10.1090/conm/223/03131openalex-snapshot

Geometric range searching and its relatives

inferred← citeshttps://doi.org/10.1109/focs.2013.82openalex-snapshot

Approximating Minimization Diagrams and Generalized Proximity Search

inferred← citeshttps://doi.org/10.1137/1.9781611973099.30openalex-snapshot

Jaywalking your Dog – Computing the Fréchet Distance with Shortcuts

inferred← citeshttps://doi.org/10.1137/1.9781611976465.89openalex-snapshot

Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices

inferred← citeshttps://doi.org/10.1137/1.9781611977073.10openalex-snapshot

Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees

inferred← citeshttps://doi.org/10.1137/140959067openalex-snapshot

Approximating Minimization Diagrams and Generalized Proximity Search

inferred← citeshttps://doi.org/10.1137/s0097539798337212openalex-snapshot

Space-Time Tradeoffs for Emptiness Queries

inferred← citeshttps://doi.org/10.1142/s0218195903001268openalex-snapshot

COMPUTING CLOSEST POINTS FOR SEGMENTS

inferred← citeshttps://doi.org/10.1145/1064092.1064098openalex-snapshot

Incidences of not-too-degenerate hyperplanes

inferred← citeshttps://doi.org/10.1145/1137856.1137866openalex-snapshot

Colored intersection searching via sparse rectangular matrix multiplication

inferred← citeshttps://doi.org/10.1145/1137856.1137872openalex-snapshot

Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

inferred← citeshttps://doi.org/10.1145/1497290.1497291openalex-snapshot

Testing bipartiteness of geometric intersection graphs

inferred← citeshttps://doi.org/10.1145/1810959.1810973openalex-snapshot

Planar visibility

inferred← citeshttps://doi.org/10.1145/262839.262988openalex-snapshot

Space-time tradeoffs for emptiness queries (extended abstract)

inferred← citeshttps://doi.org/10.1145/2723372.2737792openalex-snapshot

DBSCAN Revisited

inferred← citeshttps://doi.org/10.1145/301250.301330openalex-snapshot

Lower bounds for high dimensional nearest neighbor search and related problems

inferred← citeshttps://doi.org/10.1145/3035918.3064050openalex-snapshot

Dynamic Density Based Clustering

inferred← citeshttps://doi.org/10.1145/3083897openalex-snapshot

On the Hardness and Approximation of Euclidean DBSCAN

inferred← citeshttps://doi.org/10.1145/3591357openalex-snapshot

Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees

inferred← citeshttps://doi.org/10.1145/3787461openalex-snapshot

Quantum Algorithms for Hopcroft's problem

inferred← citeshttps://doi.org/10.1145/513400.513421openalex-snapshot

Testing Homotopy for paths in the plane

inferred← citeshttps://doi.org/10.1145/777792.777820openalex-snapshot

Local polyhedra and geometric graphs

inferred← citeshttps://doi.org/10.20382/jocg.v14i1a2openalex-snapshot

Reverse Shortest Path Problem for Unit-Disk Graphs

inferred← citeshttps://doi.org/10.4230/lipics.esa.2025.75openalex-snapshot

An Improved Bound for Plane Covering Paths

inferred← citeshttps://doi.org/10.48550/arxiv.1304.0393openalex-snapshot

Approximating Minimization Diagrams and Generalized Proximity Search

inferred← citeshttps://doi.org/10.48550/arxiv.1407.4972openalex-snapshot

Into the Square - On the Complexity of Quadratic-Time Solvable Problems

inferred← citeshttps://doi.org/10.48550/arxiv.1912.03429openalex-snapshot

Covering Polygons by Min-Area Convex Polygons

inferred← citeshttps://doi.org/10.48550/arxiv.cs/9910017openalex-snapshot

Finite-resolution hidden surface removal

inferred← citeshttps://doi.org/10.5555/982792.982921openalex-snapshot

Testing bipartiteness of geometric intersection graphs

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.