We prove that the expected size of the 3D Delaunay triangulation of n points evenly distributed on a cylinder is Theta(n log n). This shows that the n sqrt(n) behavior of the cylinder-example of Erickson is pathological.
Average-case analysis of data-structures or algorithms is com- monly used in computational geometry when the, more clas- sical, worst-case analysis is deemed overly pessimistic. Since these analyses are often intricate, the models of random geo- metric data that can be handled are often simplistic and far from "realistic inputs". We present a...
We define and study a geometric graph over points in the plane that captures the local behavior of Delaunay triangulations of points on smooth surfaces in 3-space. Two points in a planar point set P are neighbors in the empty-ellipse graph if they lie on an axis-aligned ellipse with no point of P in its interior. The empty-ellipse graph can be...
Assume that Y is a noisy version of a point set X in convex position. How many vertices does the convex hull of Y have, that is, what is the number of extreme points of Y? We consider the case where X is an (epsilon,kappa)-sample of a sphere in Rd and the noise is random and uniform: Y is obtained by replacing each point x in X by a point...
Average-case analysis of data-structures or algorithms is commonly used in compu- tational geometry when the, more classical, worst-case analysis is deemed overly pessimistic. Since these analyses are often intricate, the models of random geometric data that can be handled are often simplistic and far from "realistic inputs". We present a new...
Let F ∪ {U } be a collection of convex sets in Rd such that F covers U . We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume of U ; we analyze how small this subset can be depending on the geometry of the elements of F , and show that smooth convex sets and axis parallel...
We present a simple technique for analyzing the size of geometric hypergraphs defined by random point sets. As an application we obtain upper and lower bounds on the smoothed number of faces of the convex hull under Euclidean and Gaussian noise and related results.
We present a simple technique for analyzing the size of geometric hypergraphs dened by random point sets. As an application we obtain upper and lower bounds on the smoothed number of faces of the convex hull under Euclidean and Gaussian noise and related results.
Let F be a covering of a unit ball U in Rd by unit balls. We prove that for any epsilon >0, the smallest subset of F leaving at most a volume epsilon of U uncovered has size O(epsilon^((1-d)/2)polylog 1/epsilon). We give an example showing that this bound is tight in the worst-case, up to a logarithmic factor, and deduce an algorithm to compute...
A simple method to produce a random order type is to take the order type of a random point set. We conjecture that many probabilitydistributions on order types defined in this way are heavily concentrated and therefore sample inefficiently the space of order types. We present two results on this question. First, we study experimentally the bias...
Let F \cup {U} be a collection of convex sets in R^d such that F covers U. We prove that if the elements of F and U have comparable size then a small subset of F suffices to cover most of the volume of U; we analyze how small this subset can be depending on the geometry of the elements of F, and show that smooth convex sets and axis parallel...
We establish an upper bound on the smoothed complexity of convex hulls in $\mathbb{R}^d$ under uniform Euclidean ($\ell^2$) noise. Specifically, let $\{p_1^*, p_2^*, \ldots, p_n^*\}$ be an arbitrary set of $n$ points in the unit ball in $\mathbb{R}^d$ and let $p_i=p_i^*+x_i$, where $x_1, x_2, \ldots, x_n$ are chosen independently from the...
Let K be a compact convex body in $Rd$, let $Kn$ be the convex hull of n points chosen uniformly and independently in K, and let $fi(Kn)$ denote the number of i-dimensional faces of $Kn$. We show that for planar convex sets, $E[f0(Kn)]$ is increasing in $n$. In dimension $d≥3 we prove that if limn→∞ E[fd−1(Kn)]Anc=1$ for some constants A and...
We present two lower bounds that hold with high probability for random point sets. We first give a new, and elementary, proof that the classical models of random point sets (uniform in a smooth convex body, uniform in a polygon, Gaussian) have a superconstant number of extreme points with high probability. We next prove that any algorithm that...
Let K be a compact convex body in Rd, let Kn be the convex hull of n points chosen uniformly and independently in K, and let fi(Kn) denote the number of i-dimensional faces of Kn. We show that for planar convex sets, E(f0(Kn)) is increasing in n. In dimension d>=3 we prove that if lim( E((f[d -1](Kn))/(An^c)->1 when n->infinity for some...
In this paper, we show that, amongst $n$ uniformly distributed unit balls in $\mathbb{R}^3$, the expected number of maximal non-occluded line segments tangent to four balls is linear. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding the visibility information of a scene,...
In this paper, we show that, amongst n uniformly distributed unit balls in R^3, the expected number of maximal non-occluded line segments tangent to four balls is linear, considerably improving the previously known upper bound. Using our techniques we show a linear bound on the expected size of the visibility complex, a data structure encoding...
The notion of limits of dense graphs was invented, among other reasons, to attack problems in extremal graph theory. It is straightforward to define limits of order types in analogy with limits of graphs, and this paper examines how to adapt to this setting two approaches developed to study limits of dense graphs. We first consider flag...
We prove that the lines tangent to four possibly intersecting convex polyhedra in $ ^3$ with $n$ edges in total form $\Theta(n^2)$ connected components in the worst case. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. More generally, we show that a set of $k$ possibly...
We prove that the lines tangent to four possibly intersecting polytopes in $R3$ with $n$ edges in total form $\Theta(n^2)$ connected components. In the generic case, each connected component is a single line, but our result still holds for arbitrary degenerate scenes. This improves the previously known $O(n^3\log n)$ bound by...