Publications

The problem of computing the minimum number of flips to transform one triangulation of a convex polygon to another is not known to be in P or NP-complete. A flip sequence determines a one-to-one correspondence between the edges of the two triangulations. As a step towards understanding the source of difficulty, we investigate the case when this edge correspondence is given, i.e., we want the flip distance between two edge-labelled triangulations of a convex polygon.

We give tight worst case bounds of \(\Theta(n\log n)\) on the flip distance between edge-labelled triangulations of a convex polygon, and edge-labelled combinatorial triangulations, in contrast to the \(\Theta(n)\) bounds for the unlabelled case. Our method is to reduce to sorting with restricted operations, similar to the length-weighted reversals relevant in comparative genomics. Our bounds imply a lower bound on a very general model of sorting that subsumes a previously known lower bound. Using our upper bound we give an \(O(\log n)\)-factor approximation algorithm for computing the flip distance between edge-labelled triangulations of a convex polygon. We also consider simultaneous flips on edge-labelled triangulations. We prove an \(O(\log^2 n)\) upper bound and an \(\Omega(\log n)\) lower bound on the worst case number of simultaneous flips, in contrast with the tight bound of \(\Theta(\log n)\) for the unlabelled case proved in SODA '06.

One advantage of smart grids is that they can reduce the peak load by distributing electricity-demands over multiple short intervals. Finding a schedule that minimizes the peak load corresponds to a variant of a strip packing problem. Normally, for strip packing problems, a given set of axis-aligned rectangles must be packed into a fixed-width strip, and the goal is to minimize the height of the strip. The electricity-allocation application can be modelled as strip packing with slicing: each rectangle may be cut vertically into multiple slices and the slices may be packed into the strip as individual pieces. The stacking constraint forbids solutions in which a vertical line intersects two slices of the same rectangle.

We give a fully polynomial time approximation scheme for this problem, as well as a practical polynomial time algorithm that slices each rectangle at most once and yields a solution of height at most 5/3 times the optimal height.

In this paper we introduce self-approaching graph drawings. A straight-line drawing of a graph is self-approaching if, for any origin vertex \(s\) and any destination vertex \(t\), there is an \(st\)-path in the graph such that, for any point \(q\) on the path, as a point \(p\) moves continuously along the path from the origin to \(q\), the Euclidean distance from \(p\) to \(q\) is always decreasing. This is a more stringent condition than a greedy drawing (where only the distance between vertices on the path and the destination vertex must decrease), and guarantees that the drawing is a 5.33-spanner.

We study three topics: (1) recognizing self-approaching drawings; (2) constructing self-approaching drawings of a given graph; (3) constructing a self-approaching Steiner network connecting a given set of points.

We show that: (1) there are efficient algorithms to test if a polygonal path is self-approaching in \(\mathbb{R}^2\) and \(\mathbb{R}\)^3, but it is NP-hard to test if a given graph drawing in \(\mathbb{R}\)^3 has a self-approaching \(uv\)-path; (2) we can characterize the trees that have self-approaching drawings; (3) for any given set of terminal points in the plane, we can find a linear sized network that has a self-approaching path between any ordered pair of terminals.

Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in 2-d.

At SODA'10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in \(d\)-dimensional Euclidean space. Their algorithm requires one pass, uses \(O(d)\) space, and was shown to have approximation factor at most \((1+\sqrt{3})/2 + \varepsilon\) ~ 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a \((1+\sqrt{2})/2\) ~ 1.207 lower bound given by Agarwal and Sharathkumar.

We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an \(O(dn)\)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in \(O(d \log n)\) expected amortized time per insertion/deletion.