Solution : If each vertex of three paths are in at most 2 paths, then we can draw three paths with 0 bends per edge.

Solution : We have looked at the 1D and 2D versions, mostly in the single color case. We distinguish the Max-Packing version from the Max-1-Coverage problem.

In 1D, we have poly-time algorithms and show that 1/2 of the total coverage (of the union of unit disks) can always be achieved in the packing version, and 2/3 can be achieved in the 1-coverage version; both bounds are tight.

In 2D, we have constant factor approximations for all versions of the problem. The challenge is getting good constants. We have a PTAS for the Max-1-Coverage (or Max-Packing) if the disks are all required to be of equal radius (or there is a bound on the ratio of the largest to the smallest radius).

Conjecture 1: There will be Omega(OPT) unit disks in an optimal solution (that achieves area OPT), both in the packing version and the 1-coverage version.

Conjecture 2: In OPT, each disk contributes at least some fixed fraction of its area to the objective function. (Trivially true for packing version; the question applies to the 1-coverage version.)

Here is a bit more detail (March 8). Discs.

Peter found this reference in Cocoon 2005 which seems relevant : "A PTAS for a Disc Covering Problem Using Width-Bounded Separators", Chen, Fu, Tang and Zhu. (March 30)

Solution : In dimension d, given n points distributed ``nicely'' on a set of polygons of dimension m of of constant total size, the complexity of the Delaunay triangulation is O(n^{(d-1)/m}). The hypothesis on the distribution of points is that on each k-face of the polygons, there is at least one and no more than kappa sampling points in any sphere or radius epsilon. We probably can remove the sampling of lower dimensional faces loosing a factor of sqrt(n). Remained problems: Smooth surfaces? Noise? Computation? Here is the SODA 2007 paper on the subject! SODA 2007.

Solution :

Given a closed convex curve C and a parameter d > 0, what is the shortest closed curve H (inside C) such that for every x in C there is a y in H at distance at most d.

When C has radius of curvature at least d everywhere, then the solution is simply the offset-curve at distance d, whose length is len(C) - 2 pi d. This is a simple consequence of the Cauchy-Crofton formula (the perimeter of a convex set is the integral of its width).

More strongly, the offset curve is the only optimal solution. We observe that to get the optimal length, the curve must lie inside each strip of width w(C, theta) - 2d, and therefore inside the region bounded by the offset curve. It can't miss any point on the offset curve, and so it must be identical to it.

When C has radius of curvature smaller than d, the offset curve is no longer a simple curve. Even in the simplest case, where C is a triangle, we do not know how to compute the solution - although it appears to be characterized completely by Fermat's law (equal angles of reflection at each corner).

Literature:

V. Polishuk, J. S. B. Mitchell. Touring convex bodies - a conic programming solution. CCCG'05?

Simeon Ntafos. Watchman routes under limited visibility. CGTA 1(1992), 149-170.

Solution :

It had been observed by Dumitrescu and Calinescu  that R2, the Releaux triangle where one circular arc is replaced by a straight line is a universal carpenter’s rule container in the sense described. It has area approximately 0.614 which  is  the smallest area known so far. Dumitrescu and Calinescu also showed a lower bound of 0.375 (for any container that can hold one particular ruler of length three).

           We proved that R1, a Releaux triangle with two circular arcs replaced by straight segments (“ice cream cone”, area 0.523) is not a universal container any more. More precisely, it is “6-universal”, i.e., can contain any rule of length 6, but it is not 7-universal.

           Restricting R1 even further, i.e., replacing half of the remaining circular arc by a straight segment, we get R1/2, which has area approximately 0.512. We showed that R1/2 is 4- but not 5-universal.

           Meanwhile we found a better 4-universal box of area approximately 0.486.

           There are many remaining open problems and gaps between lower and upper bounds. Observe that the lower bound of 0.375 holds for all the cases mentioned above.

           Details can be found here.

           Literature:

     G. Calinescu and A. Dumitrescu.

     The carpenter's ruler folding problem.

     In J. Goodman, J. Pach, and E. Welzl, editors, Combinatorial and

     Computational Geometry, Mathematical Sciences Research Institute

     Publications, pages 155--166. Cambridge University Press, 2005.

     J.E. Hopcroft, D. Joseph, and S. Whitesides.

     On the movement of robot arms in 2-dimensional bounded regions.

     SIAM J. Comput., 14(2):315--333, 1985.