ABSTRACT Long Monotone Paths in Line Arrangements (2008)
József Balogh, William Steiger
Categories and Subject Descriptors
Hungarian Academy of Sciences (2007)
G Unter Rote, William Steiger, Cun-hui Zhang
Points P 1,..., Pn in the unit square define a convex n-chain if they are below y = x and, together with P 0 = (0, 0) and Pn+1 = (1, 1), they are in convex position. Under uniform probability, we...
On the Mixing Rate of the Triangulation Walk (Abstract) (2007)
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips " of one of the n \Gamma 3 internal diagonals...
Adrian Dumitrescu, Suny Stony Brook, William Steiger
We study space/time tradeo#s for querying some combinatorial structures. In the first, given an arrangement of n lines in general position in the plane, a query for a real number t asks about...
Separation Of Lines, William Steiger, Ileana Streinu
this paper we give an algorithmic-type of separation for these two classes via the complexity of sorting the elements of S, the x-coordinates
Space-time trade-os for some ranking and searching queries (2007)
Adrian Dumitrescu, William Steiger
We study space/time tradeos for querying some combinatorial structures. In the rst, given an arrangement of n lines in general position in the plane, a query for a real number t asks about Rank(t),...
Ham-Sandwich Cuts and Other Tasks in Arrangements (2007)
Stefan Langerman, William Steiger
Given a set L = {ℓ1,...,ℓn} of n lines in general position in the plane and subsets A and B of vertices in the arrangement A(L), the goal is to find a line that simultaneously bisects both A and...
Computing a High Depth Point in the Plane (2007)
Stefan Langerman, William Steiger
Given a set S = , the depth #(Q) of a point Q is the minimum number of points of S that must be in a closed halfspace containing Q. A high depth point is a point whose depth is at least max i [#(P i...
The Borsuk-Ulam theorem has many applications in algebraic topology, algebraic geomtry, and combinatorics. Here we study some combinatorial consequences, typically asserting the existence of a...
The Borsuk-Ulam theorem has many applications in algebraic topology, algebraic geomtry, and combinatorics. Here we study some combinatorial consequences, typically asserting the existence of a...
Long monotone paths in line arrangements (2003)
Oded Regev, William Steiger, Mario Szegedy
We show how to construct an arrangement of n lines having a monotone path of length n
Optimization in Arrangements (2003)
Stefan Langerman, William Steiger
Many problems can be formulated as the optimization of functions in R² which are implicitly defined by an arrangement of lines, halfplanes, or points, for example linear programming in the plane. We...
Long monotone paths in line arrangements (2003)
József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
() N — = #+V ( * () =8-H S () = ()žŸŽi ’=;¡2 ’ ¢ ” £[ ¤ ¥ – œSH( *!Y
The Convex hull for random lines in the plane (2002)
Golin, Mordecai J., Langerman, Stefan, Steiger, William
An arrangement of n lines chosen at random from R2 has a vertex set whose convex hull has constant (expected) size.
The convex hull for random lines in the plane (2002)
Mordecai Golin, Stefan Langerman, William Steiger
Abstract. An arrangement of n lines chosen at random from R 2 has a vertex set whose convex hull has constant (expected) size. 1 Introduction and Summary. Let L = {ℓ1,...,ℓn} be a set of lines in...
The complexity of hyperplane depth in the plane (2000)
Stefan Langerman, William Steiger
Given a set of n hyperplanes h 1,..., hn
Computing a maximal depth point in the plane (2000)
Stefan Langerman, William Steiger
Given a set S = {P1
A New Ultimate Convex Hull Algorithm in R² (2000)
Uwe Rösler, William Steiger, David Kravitz
We present a very simple algorithm - NEWHULL - to find the convex hull of S = {P 1 , . . . , Pn}, n given points in R 2 . It may be thought of as a variant of Quickhull; however if the hull of S has...
On a Matching Problem in the Plane (2000)
Adrian Dumitrescu, William Steiger
Let S be a set with n = w+ b points in general position in the plane, w of them white, and b of them black, where w and b are even numbers. We show that there exists a matching of points of the same...
On the mixing rate of the triangulation walk (1999)
Abstract Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips " of one of the n \Gamma 3 internal...
On the mixing rate of the triangulation walk (1999)
Let T n denote the set of triangulations of a convex polygon K with n sides. We study the random walk on T n whose transitions are \ ips" of one of the n 3 internal diagonals of the current...
Properties of random triangulations and trees (1999)
Luc Devroye, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural "geometric " features of a triangulation # Tn, for example...
An Optimal Algorithm for the Hyperplane Depth in R² (1999)
Stefan Langerman, William Steiger
Given an arrangement of n hyperplanes h 1 , . . . , h n # R d the hyperplane depth of a point P # R d is the minimum number of hyperplanes that a ray from P can meet. The hyperplane depth of the...
Random Triangulations and Trees (1999)
Luc Devroye, Philippe Flajolet, Ferran Hurtado, Marc Noy, William Steiger, Politecnica Catalunya, ...
gulation ø of K, let d i denote the degree of vertex v i , the number of (the n \Gamma 3 internal) diagonals of ø that are incident with v i . We study \Delta n (ø) = max(d i ; i = 0; : : : ; n...
Properties of random triangulations and trees (1999)
Luc Devroye, Marc Noy, Ferran Hurtado, William Steiger
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural “geometric ” features of a triangulation τ ∈ Tn, for example ∆n(τ)...
A Central Limit Theorem for Convex Chains in the Square (1998)
Imre Barany, G Rote, Günter Rote, William Steiger, William Steiger, Cun-hui Zhang, ...
Points P 1 , ...,Pn in the unit square define a convex n-chain if they are below y = x and, together with P 0 = (0, 0) and Pn+1 = (1, 1), they are in convex position. Under uniform probability, we...
A Central Limit Theorem for Convex Chains in the Square (1998)
Imre Bárány, G Rote, Günter Rote, William Steiger, William Steiger, ...
Points P 1 , ..., P n in the unit square define a convex n-chain if they are below y = x and, together with P 0 =(0, 0) and P n+1 = (1, 1), they are in convex position. Under uniform probability, we...
On the Mixing Rate of the Triangulation Walk (1998)
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips" of one of the n-3 internal diagonals of the current...
Illumination by Floodlights (1998)
William Steiger, Ileana Streinu
We consider three problems about the illumination of planar regions with floodlights of prescribed angles. Problem 1 is the decision problem: given a wedge W of angle OE ß, n points p 1 ; \Delta...
Imre Bárány, Günter Rote, Cun-hui Zhang, William Steiger
Points P1,...,Pn in the unit square define a convex n-chain if they are below y = x and, together with P0 =(0,0) and Pn+1 =(1,1), they are in convex position. Under uniform probability, we prove an...
Random Triangulations (Extended Abstract) (1996)
Luc Devroye, Philippe Flajolet, Inria Rocquencourt, Ferran Hurtado, Marc Noy, William Steiger
) 3 Luc Devroye McGill University luc@kriek.cs.mcgill.ca Philippe Flajolet INRIA - Rocquencourt Philippe.Flajolet@inria.fr Ferran Hurtado Universitat Politecnica de Catalunya hurtado@ma2.upc.es Marc...
Some Geometric Lower Bounds (1995)
. Dobkin and Lipton introduced the connected components argument to prove lower bounds in the linear decision tree model for membership problems, for example the element uniqueness problem. In this...
A Pseudo-Algorithmic Separation of Lines From Pseudo-Lines (1994)
William Steiger, Ileana Streinu
this paper we give an algorithmic-type of separation for these two classes via the complexity of sorting the elements of S, the x-coordinates