Investigations in geometric subdivisions: linear shattering and cartographic map coloring
Stephen A. Vavasis, Robert Freimer · 2000
< 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. <