This note gives a lower bound of $\Omega(n^{\lceil 2d/3\rceil})$ on the maximal complexity of the Euclidean Voronoi diagram of $n$ non-intersecting lines in $\mathbb{R}^d$ for $d>2$.
0-dimensional persistent homology is known, from a computational point of view, as the easy case. Indeed, given a list of $n$ edges in non-decreasing order of filtration value, one only needs a union-find data structure to keep track of the connected components and we get the persistence diagram in time $O(n\alpha(n))$. The running time is thus...
A good sample is a point set such that any ball of radius $\epsilon$ contains a constant number of points. The Delaunay triangulation of a good sample is proved to have linear size, unfortunately this is not enough to ensure a good time complexity of the randomized incremental construction of the Delaunay triangulation. In this paper we prove...
Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit...
We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among $n$ disjoint \emph{unit} balls has complexity $\Omega(n^4)$, which matches the...
We present two new fundamental lower bounds on the worst-case combinatorial complexity of sets of free lines and sets of maximal free line segments in the presence of balls in three dimensions. We first prove that the set of maximal non-occluded line segments among $n$ disjoint \emph{unit} balls has complexity $\Omega(n^4)$, which matches the...
Boissonnat and Pritam introduced an algorithm to reduce a filtration of flag (or clique) complexes, which can in particular speed up the computation of its persistent homology. They used so-called edge collapse to reduce the input flag filtration and their reduction method required only the 1-skeleton of the filtration. In this paper we revisit...
No description
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...
When an observer is in a 3D scene, a topological change in the view arises when the line of sight is tangent to four objects. If we consider polyhedral scenes, the relevant lines of sight are ransversals to some edges of the polyhedra. In this paper we investigate predicates about visibility events arising in this context. Namely, we consider...
The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body in Rd is polynomial for a smooth body and polylogarithmic for a polytope. We construct a body whose expected size of the convex hull oscillates between these two behaviors when the number of points increases.
The asymptotic behavior of the size of the convex hull of uniformly random points in a convex body in Rd is known for polytopes and smooth convex bodies. These are the lower and the upper bound for a general convex body. In this paper, we exhibit an example of convex body whose size of the random convex hull alternates behavior close to the...
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...
Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are usually space-optimal and time-optimal in the...
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.
A cover for a family $\mathcal{F}$ of sets in the plane is a set into which every set in $\mathcal{F}$ can be isometrically moved. We are interested in the convex cover of smallest area for a given family of triangles. Park and Cheong conjectured that any family of triangles of bounded diameter has a smallest convex cover that is itself a...
The randomized incremental construction (RIC) for building geometric data structures has been analyzed extensively, from the point of view of worst-case distributions. In many practical situations however, we have to face nicer distributions. A natural question that arises is: do the usual RIC algorithms automatically adapt when the point...
We say that a simplicial complex is shrinkable if there exists a sequence of admissible edge contractions that reduces the complex to a single vertex. We prove that it is NP-complete to decide whether a (two-dimensional) simplicial complex is shrinkable. Along the way, we describe examples of contractible complexes that are not shrinkable.
A cover for a family F of sets in the plane is a set into which every set in F can be isometrically moved. We are interested in the convex cover of smallest area for a given family of triangles. Park and Cheong conjectured that any family of triangles of bounded diameter has a smallest convex cover that is itself a triangle. The conjecture is...