Investigations in geometric subdivisions: Linear shattering and cartographic map coloring

We consider three computational geometry problems: shattering, coloring cartographic maps and Bruce's suntan lotion problem.; A subdivision S⊆Rd shatters a set of n objects if each object is contained within the closure of its own cell of 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 R2 is NP-Complete. A restricted version using axes-parallel hyperplanes is also NP-Complete. The actual number of shattering hyperplanes required varies between O&parl0;n1/d&parr0; and n - 1. We present algorithms that produce locally optimal solutions with at most n - 1 shattering hyperplanes. For R2 , we achieve O&parl0;n2logn+N2&parr0; time complexity. We have implemented a simplified version. For Rd , d ≥ 3, we have an O&parl0;Nd&parl0;n+logN&parr0;&parr0; 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 R2 . 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 ≥ 5 that &sqbl0;32k&sqbr0; colors suffice. By combining m-pires with node adjacency and islands, we can model actual GIS instances. We implemented Brelaz's Dsatur heuristic, since no specific algorithm exists for coloring our resulting cartographic graphs.; Given convex polygon P , let D1,D2 be disks centered on P 's boundary with radii r1 and r2, chosen so that P⊆D1∪D2 and r1 + 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.