MST and TSP

Due: written 5pm Friday 3/30, program 11:59pm Wednesday 4/4

Homework 4

Written Part

If I get written hw1 graded and back to you by Monday, then these are due 5pm Friday, on paper. Otherwise you do not have to do these, except for review. Or alternatively, you can do them as a ``makeup'' for a previous written homework (you have to tell me which one).

1

Suppose $G$ is a connected undirected graph, and each edge $e$ has a non-negative length $w(e)$. Let $d_G(u,v)$ denote the shortest path distance between vertices $u$ and $v$ in graph $G$ (if they are not connected, say the distance is $+\infty$). . Also, suppose $t$ is a real number, $t\geq 1$. Consider this algorithm:

xxxxxx xxxx 
		 Let $G'$ contain all the vertices of $G$, but (initially) no edges. 


Let $E$ be the set of edges in $G$, sorted by weight. 


For each edge $e$ in $E$: 


Let $u$ and $v$ be the endpoints of $e$. 


If $d_{G'}(u,v) > t\cdot w(e)$, then add $e$ to $G'$.

In the following questions, $G'$ denotes the final version of $G'$.

1(a).

Argue that for any $t\geq 1$, $G'$ contains the MST of $G$.

1(b).

Argue that for any pair of vertices $u$ and $v$, $d_G(u,v) \leq d_{G'}(u,v) \leq t \cdot d_G(u,v)$.

2

Suppose we have $n$ points in the plane. Between any two points, we allow an edge whose weight is the Euclidean distance between its endpoints (think of the edge as a line segment). Their EMST (Euclidean MST) is their minimum spanning tree using such edges.

For simplicity, suppose no 4 of the $n$ points lie on a circle. Their Delaunay triangulation is a graph on the points, containing edge $pq$ whenever there is a circle with points $p$ and $q$ on its boundary, but no point in its interior.

2(a).

Argue that the Delaunay triangulation is planar. That is, edges do not intersect except at their endpoints.

2(b).

Argue that the Delaunay triangulation contains the Euclidean MST.

2(c).

Suppose we have the Delaunay triangulation. Argue that we can compute the EMST in $O(n \lg n)$ time.

3

Suppose we again have $n$ points in the plane. We consider geometric graphs: the vertices are the $n$ points, and the weight of each edge is its length.

3(a).

Fix some parameter $\delta$, and build a graph $G_\delta$ containing all edges of length at most $\delta$. Argue that if $G_\delta$ is connected, then its MST is the EMST.

3(b).

Fix some integer $D$, and build graph $G_D$ containing, for each vertex $v$, edges to its $D$ closest neighbors. Argue, by example, that even if $G_D$ is connected, its MST may not be the EMST.

Program Part

The homework files are not quite ready, expect them ready by Monday. The basic idea is this: I will give you a program which computes a geometric graph on points in the plane (but by a rather slow method). From that geometric graph, we can compute the MST (by Kruskal's algorithm in the book). Then from the MST, I want you to compute an approximate solution to the TSP.

For extra credit, you may also try to speed up the MST computation. More details Monday.