William L. Steiger

SODA Conference 2000 Conference Paper

An optimal algorithm for hyperplane depth in the plane

• Stefan Langerman
• William L. Steiger

STOC Conference 1992 Conference Paper

Ham-Sandwich Cuts in R^d

• Chi-Yuan Lo
• Jirí Matousek 0001
• William L. Steiger

FOCS Conference 1989 Conference Paper

An Upper Bound on the Number of Planar k-Sets

• János Pach
• William L. Steiger
• Endre Szemerédi

Given a set S of n points, a subset X of size k is called a k-set if there is a hyperplane II that separates X from X/sup c/. It is proved that O(n square root k/log/sub */k) is an upper bound for the number of k-sets in the plane, thus improving the previous bound of P. Erdos et al. (A Survey of Combinatorial Theory, North-Holland, 1983, p. 139-49) by a factor of log/sub */k. The method can be extended to give the bound O(n square root k/(log k)/sup epsilon /). The proof only establishes the weaker result; it uses the geometry and combinatorics together in a stronger way than in the earlier work. >

STOC Conference 1988 Conference Paper

Two Infinite Sets of Primes with Fast Primality Tests

• Janos Pintz
• William L. Steiger
• Endre Szemerédi

STOC Conference 1986 Conference Paper

Deterministic Selection in O(log log N) Parallel Time

• Miklós Ajtai
• János Komlós
• William L. Steiger
• Endre Szemerédi