> We consider three computational geometry problems: shattering, coloring > cartographic maps and Bruce's suntan lotion problem. > > A subdivision ${\cal S}\subseteq\Re^d$ {\em shatters} a set of $n$ > objects if each object is contained within the closure of its own cell > of ${\cal S}$. We consider the problem of shattering polyhedra with > $N$ total vertices using an arrangement of hyperplanes. We show that > finding a minimum shattering of points in $\Re^2$ is \NP-Complete. A > restricted version using axes-parallel hyperplanes is also > \NP-Complete. The actual number of shattering hyperplanes required > varies between $O(n^{1/d})$ and $n-1$. We present algorithms that > produce locally optimal solutions with at most $n-1$ shattering > hyperplanes. For $\Re^2$, we achieve $O(n^2\log{n}+N^2)$ time > complexity. We have implemented a simplified version. For > $\Re^d,d\ge3$, we have an $O(N^d(n+\log{N}))$ time algorithm. We give > an $O(N^4)$ time approximation algorithm which guarantees a solution > within a factor of $1+\ln{n}$ of optimal for $\Re^2$. Detecting > whether a set of line segments is shatterable is shown to be > \3SUM-Hard. > > We consider cartographic map coloring for use in Geographical > Information Systems. The published proofs of the famous four-color > theorem yield impractical polynomial-time algorithms. Instead, we > implemented Thomassen's linear-time five-coloring algorithm. Political > maps often require generalizations to the standard four-coloring > problem. We allow each country to have $m$ disjoint pieces, which is > Heawood's $m$-pire problem. We also count node adjacency between > countries; such adjacency graphs are known as map graphs. If $k$ > regions meet at a point, we conjecture for $k\ge5$ that > $\lfloor\frac{3}{2}k\rfloor$ colors suffice. By combining $m$-pires with > node adjacency and islands, we can model actual GIS instances. We > implemented Br{'e}laz's $Dsatur$ heuristic, since no specific algorithm > exists for coloring our resulting {\em cartographic graphs}. > > Given convex polygon \P, let \D1, \D2\ be disks centered on \P's > boundary with radii $r_1$ and $r_2$, chosen so that > $\P\subseteq\D1\cup\D2$ and $r_1+r_2$ is minimized. Bruce's Suntan > Lotion problem asks for the disks' locations and sizes. We describe the > optimal cover for a triangle when $r_2=0$ and generalize the solution to > convex polygons; the minimum covering disk can be found in linear time. > We show the best one-disk solution is always optimal; no superior > two-disk solution exits. >