The Clarkson–Shor Technique Revisited and Extended
Combinatorics Probability ComputingPublished 1 March 2003
Micha Sharir
Citations31
SJR quartileQ1
SJR score1.13
SNIP1.08
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work provides an alternative simpler and more general version of the Clarkson-Shor probabilistic technique and uses it to obtain in addition several extensions and new combi- natorial bounds.
Abstract
We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.
Keywords
Computer Science
American Mathematical MonthlyAlgorithms in Combinatorial Geometry.
1,801 Citations1989Jacob E. Goodman, Herbert Edelsbrunner
Applications of random sampling in computational geometry, II
932 Citations1988Kenneth L. Clarkson
Asymptotically tight bounds for (≤k)-sets are given, which are certain halfspace partitions of point sets, and a simple proof of Lee's bounds for high-order Voronoi diagrams is given.
Davenport-Schinzel Sequences and their Geometric Applications
902 Citations1988Micha Sharir
North-Holland mathematics studiesCrossing-Free Subgraphs
280 Citations1982Miklós Ajtai, Vašek Chvátal +2 more
Combinatorics Probability ComputingCrossing Numbers and Hard Erdős Problems in Discrete Geometry
274 Citations1997Łászló A. Székely
It is shown that an old but not well-known lower bound for the crossing number of a graph yields short proofs for a number of bounds in discrete plane geometry which were considered hard before: the number of incidences among points and lines, the maximum number of unit distances among n points.
Journal of Combinatorial Theory Series AThe number of small semispaces of a finite set of points in the plane
96 Citations1986Noga Alon, Ervin Győri
Discrete & Computational GeometryAn Improved Bound for k-Sets in Three Dimensions
70 Citations2001Micha Sharir, Shakhar Smorodinsky +1 more
Discrete & Computational GeometryCounting triangle crossings and halving planes
66 Citations1994Tamal K. Dey, Herbert Edelsbrunner
Discrete & Computational GeometryExtremal Problems for Geometric Hypergraphs
48 Citations1998Tuli Dey, János Pach
