Publications



                                                                                                                  

         We establish further structural properties of families of convex sets that satisfy the conditions of Lovasz colourful Helly Theorem.


         We establish a proper analogue of the Crossing Lemma for contact graphs of Jordan curves. For any family with at least linearly

        many touching pairs we show that the number of touchings grows asymptotically faster than the number of crossings.


        Proc. 25th Annual European Symposium on Algorithms (ESA 2017)


             Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)   

          If two closed Jordan curves in the plane have precisely one point in common, then it is called a touching point. All other   intersection points are called                  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  Omega((\log\log n)^{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))n^2.

     

         Extended abstract appeared in Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015)

          It has long been conjectured that any family of n pairwise intersecting curves in the plane admits at least (2-o(1))n 

          pairwise-intersection points. The conjecture follows from the following stronger claim: the number of proper crossing points 

          is asymptotically larger than the number of touching pairs of curves (which intersect at a single touching point). 

         The SODA paper confirms the asymptotic claim for all families of monotone or convex curves.

         

 

        Full version invited to, and appeared in Journal of ACM 62 (3) (2015), Article 25.

        The paper solves this open problem. For any finite set of points moving along lines at uniform speed,

          we establish an almost-sharp near quadratic upper bound on the total number of discrete changes experienced

          by their Delaunay triangulation.

          

          Our analysis is far more general and is cast in a purely topological setting. The presentation is self-contained, with main ideas

       delivered  already in  Sections 1-4.

     Kinetic Voronoi Diagrams and Delaunay Triangulations under Polygonal Distance Functions,      

Discrete and Computational Geometry 4 (4) (2015), 871 - 904.                                                                                                                            

                                                                                            

    Full version has appeared in Discrete & Computational Geometry 49(4) (2013), pp. 710--746.

         

           This very accessible paper obtains a weaker topological variant of the FOCS 2013 result.

  

         A preliminary version has appeared in Proc. 51st Annual IEEE Symposium on Foundations of Computer Science

     (FOCS   2010), pp. 355--364. 

 

          We improve Wenger's 20-year old bound on the maximum number of geometric permutations that can be realized by line transversals

       to n pairwise disjoint convex sets,  in any dimension d larger than 2.

 

        A preliminary version appeared in Proc. 26th Annu. Symp. on Computational Geometry (SoCG 2010), pp. 58--67.

       

        We resolve a problem posed by Agarwal, Aronov, Koltun and Sharir, by extending their result to spheres of arbitrary radii in 3d.

        

         Full version appeared in Computational Geometry: Theory & Applications 44(4) (2011), 191--205.

 

         We introduce a relatively simple triangulation of a planar point set, which experiences only

        near-quadratically many changes during any (fixed degree-)algebraic motion of the underlying point set.

 

        Also in Proc. 20th ACM-SIAM Symp. on Discrete Algorithms, (SODA 2009), 170--179.

 

        We study the combinatorial complexity of the space of lines transversals to a family of k convex  polyhedra with a total of n facets.

 

          A preliminary version appeared at SODA 2007.

 

         We are to preprocess a set of colored points so as to report the number of distinct colors of points in

        query hyperboxes. The complexity of this problem happens to be strongly related to that of matrix multiplication.

        As a by-product, we establish several important results on the worst-case and expected number of maximal empty 

        hyperboxes induced by a set of points in d-space. 

        In addition, we provide an optimal decomposition of the union of orthants into pairwise disjoint hyperboxes.

 

    

        

       A preliminary version appeared at ESA 2007.