Geometric Algorithms and Linear Programming

Prev: Data Structures Next: Graph Algorithms

Problems

9.1

Prove Theorem 8.8 using backwards analysis.

---

9.2

By “dualizing” the randomized incremental algorithm for convex hulls in the plane (Section 9.2), derive a randomized incremental algorithm for computing the intersection of $n$ given half-planes. Show that its expected running time is $O(n\log n)$.

---

9.3

Use the Mulmuley games of Section 8.2.1 to derive Theorem 9.8.

---

9.4

The object of this problem is to show that the time bound in Theorem 9.1 holds with high probability. For a point $p\in S$, define the indicator variable $X_j(p)$ as follows:

$$X_j(p)=\{\begin{array}{ll}1& \text{if }p\text{’s pointer is updated at the }j\text{th step;}\\ 0& \text{otherwise.}\end{array}$$

Thus the total work done in updating $p$‘s pointer is ${\sum }_j{X}_j(p)$. By showing that ${\sum }_j{X}_j(p)$ is $O(\log n)$ with probability $1-n^{-2}$, show that the total work is $O(n\log n)$ with high probability.

---

9.5

Show that the randomized incremental half-space intersection algorithm of Section 9.4 can be adapted to construct $I_p(S)$, the intersection of $n$ spheres in three dimensions, in expected time $n\log n$.

---

9.6

Show that the set $S_0$ resulting from Steps 2 and 3 in the randomized diameter algorithm (Section 9.8) can be found in time linear in the size of $S$, for the $L_1$ metric.

---

9.7

Let $S$ be a set of $n$ points in the plane. For any positive integer $k<n$, show that there is a subset $S_k$ consisting of $k$ points in $S$ with the property that no triangle in $\mathrm{del}(S_k)$ contains more than $(cn\log k)/k$ points, for a suitably chosen constant $c$.

---

9.8

In this problem, we discuss the removal of the simplifying assumptions made at the beginning of our discussion of linear programming algorithms. We focus on the non-degeneracy assumptions 3-4. Consider a set of $d+1$ constraints whose defining hyperplanes intersect at a common point $p$; without loss of generality, let these be defined by the first $d+1$ rows of $A$ (together with the first $d+1$ components of $b$). Consider adding ${ϵ}^i$ to the $i$th component of $b$, for $1\le i\le d+1$, where $ϵ$ is a small positive real. Show that for every choice of $A$ and $b$, there is a choice $ϵ$ such that (i) the hyperplanes intersecting at $p$ no longer intersect at a single point, and (ii) if $p$ were the optimum of the linear program determined by $A$ and $b$, the new optimum is defined by $d$ of the constraints that originally intersected at $p$.

---

9.9

Prove Lemma 9.16. (Hint: For every constraint $h$ of weight $w_h>1$, replace it by $w_h$ “virtual copies” of $h$ each of weight $1$, and consider sampling this multiset.)

---

9.10

The Boolean $n$-cube is an undirected graph that has $N=2^n$ nodes connected in the following manner. Let $(i_0,\dots ,i_{n-1})$ be the ordered binary representation of vertex $i$, i.e.,

$$i=\sum _{j=0}^{n-1}{i}_j{2}^j,i_j\in \{0,1\}.$$

Then there is an edge between vertex $i$ and vertex $j$ if and only if $(i_0,\dots ,i_{n-1})$ and $(j_0,\dots ,j_{n-1})$ differ in exactly one position. Thus every vertex in the $n$-cube has degree $n={\log }_{2}N$. An acyclic orientation of the cube is an assignment of a direction to each edge, such that the resulting directed graph is acyclic. A sink in the digraph is a node with no edges directed out of it. Consider a random walk on an $n$-cube with an acyclic orientation: at each step, the walk proceeds along an outgoing edge chosen uniformly at random. Show that for every $n$, there is an acyclic orientation of the $n$-cube and a starting vertex such that expected number of steps for the walk to reach a sink is $2^{\Omega (n)}$.

This has the following significance. The $n$-cube can be realized as a polyhedron defined by the intersection of $2n$ half-spaces in $n$ dimensions. Consider the Random Simplex algorithm on this polyhedron. The directions on the edges are meant to model directions of improving objective function. The above lower bound suggests that if we had to give a sub-exponential upper bound on the performance of the Random Simplex algorithm, we would have to take into account the geometry of the polytope, using it to preclude the kind of arbitrary acyclic orientation that led to the lower bound.

---

9.11

In this problem, we consider the extension of the BasisLP algorithm to optimization problems more general than linear programming. Consider the following framework for an abstract optimization problem. There is a set $H$ of $n$ constraints, and a function $\mathcal{O}$ that maps every subset $G$ of $H$ to the real numbers; we think of $\mathcal{O}$ as the optimum value for $G$. Let $F\subseteq G\subseteq H$, and $h\in H$. For any such $F$, $G$, and $h$, we further require that

1. $\mathcal{O}(F)\le \mathcal{O}(G)$, and
2. $\mathcal{O}(F)=\mathcal{O}(G)$ implies that

$$\mathcal{O}(F\cup \{h\})>\mathcal{O}(F)⟺\mathcal{O}(G\cup \{h\})>\mathcal{O}(G).$$

Defining the concept of a basis as for linear programming, let us call the maximum cardinality of any basis the combinatorial dimension of the instance.

Modify the BasisLP algorithm so that it works for such abstract optimization problems, and show that the analysis of BasisLP may be applied with $d$ replaced by the combinatorial dimension.

---

9.12

Consider the smallest enclosing ball problem: given $n$ points in $d$-dimensional space, find the radius of the smallest ball that contains all $n$ points. By showing that this fits the paradigm of an abstract optimization problem, show that a suitably modified version of the BasisLP algorithm can be used to solve it.