BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that for any finite set P of points in the plane and ε>0 there exist O(ε3/2+γ1) points in R2, for arbitrary small γ>0, that pierce every convex set K with ∣K∩P∣≥ε∣P∣. This is the first improvement of the bound of O(ε21) that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.
If two closed Jordan curves in the plane have precisely one point in common, then it is called a {\em touching point}. All other intersection points are called {\em crossing points}. The main result of this paper is a Crossing Lemma for closed curves: In any family of n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, the number of crossing points exceeds the number of touching points by a factor of at least Ω((loglogn)1/8). As a corollary, we prove the following long-standing conjecture of Richter and Thomassen: The total number of intersection points between any n pairwise intersecting simple closed curves in the plane, no three of which pass through the same point, is at least (1−o(1))n2.
Let P be a set of n points in R2, and let DT(P) denote its Euclidean Delaunay triangulation. We introduce the notion of an edge of DT(P) being {\it stable}. Defined in terms of a parameter α>0, a Delaunay edge pq is called α-stable, if the (equal) angles at which p and q see the corresponding Voronoi edge epq are at least α. A subgraph G of DT(P) is called {\it (cα,α)-stable Delaunay graph} (SDG in short), for some constant c≥1, if every edge in G is α-stable and every cα-stable of DT(P) is in G. We show that if an edge is stable in the Euclidean Delaunay triangulation of P, then it is also a stable edge, though for a different value of α, in the Delaunay triangulation of P under any convex distance function that is sufficiently close to the Euclidean norm, and vice-versa. In particular, a 6α-stable edge in DT(P) is α-stable in the Delaunay triangulation under the distance function induced by a regular k-gon for k≥2π/α, and vice-versa. Exploiting this relationship and the analysis in~\cite{polydel}, we present a linear-size kinetic data structure (KDS) for maintaining an (8α,α)-SDG as the points of P move. If the points move along algebraic trajectories of bounded degree, the KDS processes nearly quadratic events during the motion, each of which can processed in O(logn) time. Finally, we show that a number of useful properties of DT(P) are retained by SDG of P.
Let P be a set of n points and Q a convex k-gon in R2. We analyze in detail the topological (or discrete) changes in the structure of the Voronoi diagram and the Delaunay triangulation of P, under the convex distance function defined by Q, as the points of P move along prespecified continuous trajectories. Assuming that each point of P moves along an algebraic trajectory of bounded degree, we establish an upper bound of O(k4nλr(n)) on the number of topological changes experienced by the diagrams throughout the motion; here λr(n) is the maximum length of an (n,r)-Davenport-Schinzel sequence, and r is a constant depending on the algebraic degree of the motion of the points. Finally, we describe an algorithm for efficiently maintaining the above structures, using the kinetic data structure (KDS) framework.
A long standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least (1−o(1))n2. We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class is touching every curve from the second class. (Two curves are said to be touching if they have precisely one point in common, at which they do not properly cross.) An important ingredient of our proofs is the following statement: Let S be a family of the graphs of n continuous real functions defined on R, no three of which pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is Ω(ntlogt/loglogt).
Let P be a collection of n points moving along pseudo-algebraic trajectories in the plane. One of the hardest open problems in combinatorial and computational geometry is to obtain a nearly quadratic upper bound, or at least a subcubic bound, on the maximum number of discrete changes that the Delaunay triangulation $\DT(P)$ of P experiences during the motion of the points of P. In this paper we obtain an upper bound of $O(n^{2+\eps})$, for any $\eps>0$, under the assumptions that (i) any four points can be co-circular at most twice, and (ii) either no triple of points can be collinear more than twice, or no ordered triple of points can be collinear more than once.
We consider the problem of maintaining the Euclidean Delaunay triangulation $\DT$ of a set P of n moving points in the plane, along algebraic trajectories of constant description complexity. Since the best known upper bound on the number of topological changes in the full $\DT$ is nearly cubic, we seek to maintain a suitable portion of it that is less volatile yet retains many useful properties. We introduce the notion of a stable Delaunay graph, which is a dynamic subgraph of the Delaunay triangulation. The stable Delaunay graph (a) is easy to define, (b) experiences only a nearly quadratic number of discrete changes, (c) is robust under small changes of the norm, and (d) possesses certain useful properties. The stable Delaunay graph ($\SDG$ in short) is defined in terms of a parameter α>0, and consists of Delaunay edges pq for which the angles at which p and q see their Voronoi edge epq are at least α. We show that (i) $\SDG$ always contains at least roughly one third of the Delaunay edges; (ii) it contains the β-skeleton of P, for β=1+Ω(α2); (iii) it is stable, in the sense that its edges survive for long periods of time, as long as the orientations of the segments connecting (nearby) points of P do not change by much; and (iv) stable Delaunay edges remain stable (with an appropriate redefinition of stability) if we replace the Euclidean norm by any sufficiently close norm. In particular, we can approximate the Euclidean norm by a polygonal norm (namely, a regular k-gon, with k=Θ(1/α)), and keep track of a Euclidean $\SDG$ by maintaining the full Delaunay triangulation of P under the polygonal norm. We describe two kinetic data structures for maintaining $\SDG$. Both structures use O∗(n) storage and process O∗(n2) events during the motion, each in O∗(1) time.
We present a simple randomized scheme for triangulating a set P of n points in the plane, and construct a kinetic data structure which maintains the triangulation as the points of P move continuously along piecewise algebraic trajectories of constant description complexity. Our triangulation scheme experiences an expected number of O(n2βs+2(n)log2n) discrete changes, and handles them in a manner that satisfies all the standard requirements from a kinetic data structure: compactness, efficiency, locality and responsiveness. Here s is the maximum number of times where any specific triple of points of P can become collinear, βs+2(q)=λs+2(q)/q, and λs+2(q) is the maximum length of Davenport-Schinzel sequences of order s+2 on n symbols. Thus, compared to the previous solution of Agarwal et al.~\cite{AWY}, we achieve a (slightly) improved bound on the number of discrete changes in the triangulation. In addition, we believe that our scheme is simpler to implement and analyze.
We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in Rd, for d≥3, is O(n2d−3logn), improving Wenger's 20 years old bound of O(n2d−2).
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.