On the public citation graph
Quasi-optimal range searching in spaces of finite VC-dimension
0 signed · 192 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/978-3-319-21852-6_3openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1007/978-3-642-61568-9openalex-snapshot
Algorithms in Combinatorial Geometry
inferredcites →https://doi.org/10.1007/978-3-642-69900-9openalex-snapshot
Data Structures and Algorithms 3
inferredcites →https://doi.org/10.1007/bf02187742openalex-snapshot
Implicitly representing arrangements of lines or segments
inferredcites →https://doi.org/10.1007/bf02187747openalex-snapshot
Visibility and intersection problems in plane geometry
inferredcites →https://doi.org/10.1016/0020-0190(86)90088-8openalex-snapshot
Halfplanar range search in linear space and O(n0.695) query time
inferredcites →https://doi.org/10.1016/0097-3165(72)90019-2openalex-snapshot
On the density of families of sets
inferredcites →https://doi.org/10.1016/0196-6774(80)90005-xopenalex-snapshot
Combinatorial solutions of multidimensional divide-and-conquer recurrences
inferredcites →https://doi.org/10.1016/0304-3975(82)90120-7openalex-snapshot
Fast detection of polyhedral intersection
inferredcites →https://doi.org/10.1109/sfcs.1987.48openalex-snapshot
Polytope range searching and integral geometry
inferredcites →https://doi.org/10.1137/0210001openalex-snapshot
Lower Bounds on the Complexity of Some Optimal Data Structures
inferredcites →https://doi.org/10.1137/0214022openalex-snapshot
On the Complexity of Maintaining Partial Sums
inferredcites →https://doi.org/10.1137/1116025openalex-snapshot
On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
inferredcites →https://doi.org/10.1145/22145.22163openalex-snapshot
A general approach to d-dimensional geometric queries
inferredcites →https://doi.org/10.1145/321879.321884openalex-snapshot
Efficiency of a Good But Not Linear Set Union Algorithm
inferredcites →https://doi.org/10.1145/323233.323252openalex-snapshot
Visibility and intersectin problems in plane geometry
inferredcites →https://doi.org/10.1145/41958.41994openalex-snapshot
Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension
inferredcites →https://doi.org/10.1145/73393.73400openalex-snapshot
Implicitly representing arrangements of lines or segments
inferredcites →https://doi.org/10.1145/800061.808755openalex-snapshot
A 3-space partition and its applications
inferredcites →https://doi.org/10.1145/800070.802185openalex-snapshot
Space-time tradeoff for answering range queries (Extended Abstract)
inferredcites →https://doi.org/10.1214/aop/1176995384openalex-snapshot
Central Limit Theorems for Empirical Measures
inferredcites →https://doi.org/10.2307/2325168openalex-snapshot
Algorithms in Combinatorial Geometry.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jagm.1996.0027openalex-snapshot
Derandomization in Computational Geometry
inferred← citeshttps://doi.org/10.1006/jagm.1996.0028openalex-snapshot
Selection in Monotone Matrices and Computingkth Nearest Neighbors
inferred← citeshttps://doi.org/10.1006/jagm.1996.0063openalex-snapshot
Range Searching and Point Location among Fat Objects
inferred← citeshttps://doi.org/10.1007/11534273_23openalex-snapshot
Orthogonal Subdivisions with Low Stabbing Numbers
inferred← citeshttps://doi.org/10.1007/3-540-48762-x_71openalex-snapshot
Efficient Image Retrieval through Vantage Objects
inferred← citeshttps://doi.org/10.1007/3-540-52846-6_107openalex-snapshot
Intersection queries in sets of disks
inferred← citeshttps://doi.org/10.1007/3-540-55488-2_30openalex-snapshot
On spanning trees with low crossing numbers
inferred← citeshttps://doi.org/10.1007/3-540-55719-9_95openalex-snapshot
Lower bounds on the complexity of simplex range reporting on a pointer machine
inferred← citeshttps://doi.org/10.1007/3-540-55808-x_1openalex-snapshot
On range searching with semialgebraic sets
inferred← citeshttps://doi.org/10.1007/3-540-58218-5_17openalex-snapshot
On intersection searching problems involving curved objects
inferred← citeshttps://doi.org/10.1007/3-540-60618-1_61openalex-snapshot
VC-dimensions for graphs (extended abstract)
inferred← citeshttps://doi.org/10.1007/978-3-030-36412-0_13openalex-snapshot
Fast Diameter Computation Within Split Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-13075-0_27openalex-snapshot
On the Most Likely Voronoi Diagramand Nearest Neighbor Searching
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/978-3-319-94776-1_13openalex-snapshot
Polygon Queries for Convex Hulls of Points
inferred← citeshttps://doi.org/10.1007/978-3-540-73951-7_41openalex-snapshot
Cuttings for Disks and Axis-Aligned Rectangles
inferred← citeshttps://doi.org/10.1007/978-3-642-19222-7_36openalex-snapshot
Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures
inferred← citeshttps://doi.org/10.1007/978-3-642-22300-6_26openalex-snapshot
On Rectilinear Partitions with Minimum Stabbing Number
inferred← citeshttps://doi.org/10.1007/978-3-642-31155-0_8openalex-snapshot
A Simple Framework for the Generalized Nearest Neighbor Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-58043-7_4openalex-snapshot
Epsilon-Nets and Computational Geometry
inferred← citeshttps://doi.org/10.1007/978-3-642-61012-7_12openalex-snapshot
Suchen und Konstruieren durch Verdoppeln
inferred← citeshttps://doi.org/10.1007/bf01303517openalex-snapshot
Discrepancy and approximations for bounded VC-dimension
inferred← citeshttps://doi.org/10.1007/bf01758854openalex-snapshot
Quasi-optimal upper bounds for simplex range searching and new zone theorems
inferred← citeshttps://doi.org/10.1007/bf01931656openalex-snapshot
Storing line segments in partition trees
inferred← citeshttps://doi.org/10.1007/bf01942604openalex-snapshot
Testing Homotopic Routability Under Polygonal Wiring Rules
inferred← citeshttps://doi.org/10.1007/bf01994881openalex-snapshot
Intersection queries in sets of disks
inferred← citeshttps://doi.org/10.1007/bf02187742openalex-snapshot
Implicitly representing arrangements of lines or segments
inferred← citeshttps://doi.org/10.1007/bf02187809openalex-snapshot
Partitioning arrangements of lines II: Applications
inferred← citeshttps://doi.org/10.1007/bf02189304openalex-snapshot
Applications of a new space-partitioning technique
inferred← citeshttps://doi.org/10.1007/bf02392598openalex-snapshot
Improved upper bounds for approximation by zonotopes
inferred← citeshttps://doi.org/10.1007/bf02523679openalex-snapshot
On counting pairs of intersecting segments and off-line triangle range searching
inferred← citeshttps://doi.org/10.1007/bf02570718openalex-snapshot
Almost optimal set covers in finite VC-dimension
inferred← citeshttps://doi.org/10.1007/bf02573971openalex-snapshot
How hard is half-space range searching?
inferred← citeshttps://doi.org/10.1007/bf02573972openalex-snapshot
Range searching with efficient hierarchical cuttings
inferred← citeshttps://doi.org/10.1007/bf02574015openalex-snapshot
On range searching with semialgebraic sets
inferred← citeshttps://doi.org/10.1007/bf02574066openalex-snapshot
Tight upper bounds for the discrepancy of half-spaces
inferred← citeshttps://doi.org/10.1007/bf02574389openalex-snapshot
Vapnik-Chervonenkis dimension and (pseudo-)hyperplane arrangements
inferred← citeshttps://doi.org/10.1007/bfb0028277openalex-snapshot
Applications of a new space partitioning technique
inferred← citeshttps://doi.org/10.1007/bfb0045072openalex-snapshot
Fast range searching with Delaunay Triangulations
inferred← citeshttps://doi.org/10.1007/bfb0049412openalex-snapshot
Range searching and point location among fat objects
inferred← citeshttps://doi.org/10.1007/s00454-003-2853-5openalex-snapshot
Spanning Trees Crossing Few Barriers
inferred← citeshttps://doi.org/10.1007/s00454-003-2859-zopenalex-snapshot
Bounded VC-Dimension Implies a Fractional Helly Theorem
inferred← citeshttps://doi.org/10.1007/s00454-004-1123-5openalex-snapshot
Cutting Triangular Cycles of Lines in Space
inferred← citeshttps://doi.org/10.1007/s00454-006-1269-4openalex-snapshot
Range Counting over Multidimensional Data Streams
inferred← citeshttps://doi.org/10.1007/s00454-007-9025-yopenalex-snapshot
Tight Bounds for Connecting Sites Across Barriers
inferred← citeshttps://doi.org/10.1007/s00454-009-9158-2openalex-snapshot
Cuttings for Disks and Axis-Aligned Rectangles in Three-Space
inferred← citeshttps://doi.org/10.1007/s00454-010-9248-1openalex-snapshot
Relative (p,ε)-Approximations in Geometry
inferred← citeshttps://doi.org/10.1007/s00454-012-9412-xopenalex-snapshot
Tight Lower Bounds for Halfspace Range Searching
inferred← citeshttps://doi.org/10.1007/s00454-012-9443-3openalex-snapshot
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth–Katz Polynomial Partitioning Technique
inferred← citeshttps://doi.org/10.1007/s00454-012-9481-xopenalex-snapshot
Disjoint Edges in Complete Topological Graphs
inferred← citeshttps://doi.org/10.1007/s00454-016-9824-0openalex-snapshot
Two Proofs for Shallow Packings
inferred← citeshttps://doi.org/10.1007/s00454-019-00099-6openalex-snapshot
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
inferred← citeshttps://doi.org/10.1007/s00454-019-00103-zopenalex-snapshot
On Separating Points by Lines
inferred← citeshttps://doi.org/10.1007/s00454-021-00318-zopenalex-snapshot
The VC Dimension of Metric Balls under Fréchet and Hausdorff Distances
inferred← citeshttps://doi.org/10.1007/s00454-023-00521-0openalex-snapshot
Implicit Representation of Sparse Hereditary Families
inferred← citeshttps://doi.org/10.1007/s00454-024-00692-4openalex-snapshot
On Short Edges in Complete Topological Graphs
inferred← citeshttps://doi.org/10.1007/s00493-025-00186-8openalex-snapshot
Sunflowers in Set Systems with Small VC-Dimension
inferred← citeshttps://doi.org/10.1007/s10998-008-8217-7openalex-snapshot
Convex subdivisions with low stabbing numbers
inferred← citeshttps://doi.org/10.1016/0020-0190(94)90129-5openalex-snapshot
Rectilinear decompositions with low stabbing number
inferred← citeshttps://doi.org/10.1016/0097-3165(95)90052-7openalex-snapshot
Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension
inferred← citeshttps://doi.org/10.1016/0196-6774(92)90021-4openalex-snapshot
Good splitters for counting points in triangles
inferred← citeshttps://doi.org/10.1016/0196-6774(92)90062-hopenalex-snapshot
Algorithms for ray-shooting and intersection searching
inferred← citeshttps://doi.org/10.1016/0925-7721(92)90006-eopenalex-snapshot
Reporting points in halfspaces
inferred← citeshttps://doi.org/10.1016/0925-7721(95)00002-xopenalex-snapshot
Simplex range reporting on a pointer machine
inferred← citeshttps://doi.org/10.1016/b978-044482537-7/50014-0openalex-snapshot
Derandomization in Computational Geometry
inferred← citeshttps://doi.org/10.1016/j.comgeo.2012.03.001openalex-snapshot
Absolute approximation of Tukey depth: Theory and experiments
inferred← citeshttps://doi.org/10.1016/j.comgeo.2013.12.005openalex-snapshot
Minimum-link paths revisited
inferred← citeshttps://doi.org/10.1016/j.comgeo.2016.11.003openalex-snapshot
Many disjoint edges in topological graphs
inferred← citeshttps://doi.org/10.1016/j.dam.2021.09.017openalex-snapshot
Vapnik–Chervonenkis dimension and density on Johnson and Hamming graphs
inferred← citeshttps://doi.org/10.1016/j.disc.2015.05.026openalex-snapshot
VC-dimension and Erdős–Pósa property
inferred← citeshttps://doi.org/10.1016/j.endm.2015.07.006openalex-snapshot
Many disjoint edges in topological graphs
inferred← citeshttps://doi.org/10.1016/s0031-3203(00)00120-5openalex-snapshot
Efficient image retrieval through vantage objects
inferred← citeshttps://doi.org/10.1016/s0166-218x(96)00137-0openalex-snapshot
The VC-dimension of set systems defined by graphs
inferred← citeshttps://doi.org/10.1016/s0925-7721(00)00022-5openalex-snapshot
Approximate range searching☆☆A preliminary version of this paper appeared in the Proc. of the 11th Annual ACM Symp. on Computational Geometry, 1995, pp. 172–181.
inferred← citeshttps://doi.org/10.1016/s0925-7721(01)00009-8openalex-snapshot
Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses☆☆A preliminary version of this report was presented at the Fifth Canadian Conference on Computational Geometry [32].
inferred← citeshttps://doi.org/10.1017/9781108539180openalex-snapshot
Forbidden Configurations in Discrete Geometry
inferred← citeshttps://doi.org/10.1023/a:1009857410665openalex-snapshot
Fast Range Searching with Delaunay Triangulations
inferred← citeshttps://doi.org/10.1051/ita/1991250201031openalex-snapshot
Spanning trees with low crossing number
inferred← citeshttps://doi.org/10.1070/sm8780openalex-snapshot
Sign rank versus Vapnik-Chervonenkis dimension
inferred← citeshttps://doi.org/10.1090/conm/223/03131openalex-snapshot
Geometric range searching and its relatives
inferred← citeshttps://doi.org/10.1090/s0894-0347-1989-1001852-0openalex-snapshot
Lower Bounds on the Complexity of Polytope Range Searching
inferred← citeshttps://doi.org/10.1109/5.163409openalex-snapshot
Dynamic algorithms in computational geometry
inferred← citeshttps://doi.org/10.1109/focs.2012.32openalex-snapshot
On Range Searching with Semialgebraic Sets II
inferred← citeshttps://doi.org/10.1109/focs.2018.00030openalex-snapshot
An Improved Bound for Weak Epsilon-Nets in the Plane
inferred← citeshttps://doi.org/10.1109/iv.2012.85openalex-snapshot
Solving the Range Searching Problem for Region Bounded by a Convex Surface
inferred← citeshttps://doi.org/10.1109/sfcs.1991.185370openalex-snapshot
Reporting points in halfspaces
inferred← citeshttps://doi.org/10.1109/sfcs.1991.185401openalex-snapshot
Discrepancy and in -approximations for bounded VC-dimension
inferred← citeshttps://doi.org/10.1109/sfcs.1993.366848openalex-snapshot
Geometric discrepancy revisited
inferred← citeshttps://doi.org/10.1137/0221035openalex-snapshot
Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
inferred← citeshttps://doi.org/10.1137/06066031xopenalex-snapshot
Axis-Aligned Subdivisions with Low Stabbing Numbers
inferred← citeshttps://doi.org/10.1137/1.9781611973402.101openalex-snapshot
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
inferred← citeshttps://doi.org/10.1137/1.9781611975031.59openalex-snapshot
On Separating Points by Lines
inferred← citeshttps://doi.org/10.1137/1.9781611977585.ch25openalex-snapshot
An Optimal Lower Bound for Simplex Range Reporting
inferred← citeshttps://doi.org/10.1137/130925554openalex-snapshot
Estimating the Number of Disjoint Edges in Simple Topological Graphs via Cylindrical Drawings
inferred← citeshttps://doi.org/10.1137/140977746openalex-snapshot
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
inferred← citeshttps://doi.org/10.1137/20m136551xopenalex-snapshot
Diameter, Eccentricities and Distance Oracle Computations on H -Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension
inferred← citeshttps://doi.org/10.1137/21m145118xopenalex-snapshot
Algorithms for Subpath Convex Hull Queries and Ray-Shooting among Segments
inferred← citeshttps://doi.org/10.1137/s0097539794268649openalex-snapshot
An Expander-Based Approach to Geometric Optimization
inferred← citeshttps://doi.org/10.1142/s0218195912500069openalex-snapshot
FITTING A STEP FUNCTION TO A POINT SET WITH OUTLIERS BASED ON SIMPLICIAL THICKNESS DATA STRUCTURES
inferred← citeshttps://doi.org/10.1142/s0218195916600025openalex-snapshot
On the Most Likely Voronoi Diagram and Nearest Neighbor Searching
inferred← citeshttps://doi.org/10.1145/103418.103470openalex-snapshot
Approximations and optimal geometric divide-and-conquer
inferred← citeshttps://doi.org/10.1145/109648.109653openalex-snapshot
Intersection queries for curved objects (extended abstract)
inferred← citeshttps://doi.org/10.1145/1137856.1137920openalex-snapshot
Tight bounds for connecting sites across barriers
inferred← citeshttps://doi.org/10.1145/1240233.1240239openalex-snapshot
Deterministic sampling and range counting in geometric data streams
inferred← citeshttps://doi.org/10.1145/1247069.1247128openalex-snapshot
On approximate halfspace range counting and relative epsilon-approximations
inferred← citeshttps://doi.org/10.1145/142675.142730openalex-snapshot
How hard is halfspace range searching?
inferred← citeshttps://doi.org/10.1145/142675.142732openalex-snapshot
Range searching with efficient hierarchical cuttings
inferred← citeshttps://doi.org/10.1145/160985.161137openalex-snapshot
An expander-based approach to geometric optimization
inferred← citeshttps://doi.org/10.1145/177424.178029openalex-snapshot
Almost optimal set covers in finite VC-dimension
inferred← citeshttps://doi.org/10.1145/1810959.1810964openalex-snapshot
Tight lower bounds for halfspace range searching
inferred← citeshttps://doi.org/10.1145/1998196.1998204openalex-snapshot
Comparing distributions and shapes using the kernel distance
inferred← citeshttps://doi.org/10.1145/220279.220308openalex-snapshot
Stabbing triangulations by lines in 3D
inferred← citeshttps://doi.org/10.1145/2213977.2214090openalex-snapshot
Optimal private halfspace counting via discrepancy
inferred← citeshttps://doi.org/10.1145/2261250.2261308openalex-snapshot
Disjoint edges in complete topological graphs
inferred← citeshttps://doi.org/10.1145/2462356.2462388openalex-snapshot
Range counting coresets for uncertain data
inferred← citeshttps://doi.org/10.1145/2582112.2582152openalex-snapshot
Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
inferred← citeshttps://doi.org/10.1145/262839.263080openalex-snapshot
Time-series similarity problems and well-separated geometric sets
inferred← citeshttps://doi.org/10.1145/2675744.2675754openalex-snapshot
A toolbox for fast and approximate solutions for large linear and semidefinite programs
inferred← citeshttps://doi.org/10.1145/304893.304907openalex-snapshot
Spanning trees crossing few barriers
inferred← citeshttps://doi.org/10.1145/3406325.3451062openalex-snapshot
Stronger bounds for weak epsilon-nets in higher dimensions
inferred← citeshttps://doi.org/10.1145/3514221.3517896openalex-snapshot
Selectivity Functions of Range Queries are Learnable
inferred← citeshttps://doi.org/10.1145/3555985openalex-snapshot
An Improved Bound for Weak Epsilon-nets in the Plane
inferred← citeshttps://doi.org/10.1145/3578574openalex-snapshot
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
inferred← citeshttps://doi.org/10.1145/3787461openalex-snapshot
Quantum Algorithms for Hopcroft's problem
inferred← citeshttps://doi.org/10.1145/73833.73835openalex-snapshot
A deterministic algorithm for partitioning arrangements of lines and its application
inferred← citeshttps://doi.org/10.1145/73833.73868openalex-snapshot
Ray shooting and other applications of spanning trees with low stabbing number
inferred← citeshttps://doi.org/10.1145/780542.780622openalex-snapshot
Cutting triangular cycles of lines in space
inferred← citeshttps://doi.org/10.1145/98524.98530openalex-snapshot
How to net a lot with little: small ε-nets for disks and halfspaces
inferred← citeshttps://doi.org/10.1145/98524.98532openalex-snapshot
Quasi-optimal upper bounds for simplex range searching and new zone theorems
inferred← citeshttps://doi.org/10.1145/997817.997844openalex-snapshot
Range counting over multidimensional data streams
inferred← citeshttps://doi.org/10.1201/9781315119601openalex-snapshot
Handbook of Discrete and Computational Geometry, Third Edition
inferred← citeshttps://doi.org/10.1201/9781420035315.ch44openalex-snapshot
The discrepancy method in computational geometry
inferred← citeshttps://doi.org/10.37236/9273openalex-snapshot
A Sauer–Shelah–Perles Lemma for Lattices
inferred← citeshttps://doi.org/10.4213/sm8780openalex-snapshot
Знаковый ранг и размерность Вапника-Червоненкиса
inferred← citeshttps://doi.org/10.4230/lipics.socg.2021.8openalex-snapshot
Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
inferred← citeshttps://doi.org/10.46298/dmtcs.6631openalex-snapshot
On the VC-dimension of half-spaces with respect to convex sets
inferred← citeshttps://doi.org/10.47749/t/unicamp.1994.78800openalex-snapshot
Busca em subespaços em varias dimensões
inferred← citeshttps://doi.org/10.48550/arxiv.1412.5215openalex-snapshot
Shallow Packings in Geometry
inferred← citeshttps://doi.org/10.48550/arxiv.1701.04529openalex-snapshot
On Equal Point Separation by Planar Cell Decompositions
inferred← citeshttps://doi.org/10.48550/arxiv.1907.04385openalex-snapshot
Diameter computation on $H$-minor free graphs and graphs of bounded (distance) VC-dimension
inferred← citeshttps://doi.org/10.5555/982792.982854openalex-snapshot
Minimizing the stabbing number of matchings, trees, and triangulations
inferred← citeshttps://doi.org/10.70675/b49810c9z66a7z4dc3zaeddz8dc7fffaf3adopenalex-snapshot
Efficient Approximations of High-Dimensional Data
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.