Tuesday, November 6, 2007

Cute Problem: Wooden Convex Hull

I didn't manage to keep an earlier promise to post olympiad-style problems... But here is a cute one.

You have n trees at given coordinates in the plane. You want to build a polygonal fence around the trees. However, the only way to get wood for the fence is to cut down some trees in the first place! Let's say each tree gives you enough wood for M meters of fence. The goal is to find the minimum k, such that you can cut down some k trees, and surround the rest by a fence of M*k meters.

What is the best algorithm you can find? Express your answer in terms on n and k.

As a bonus challenge, find a fast algorithm for the case when trees give you a different amount of wood M1, ..., Mi.

4 comments:

D. Eppstein said...

An old paper of mine looks relevant, I think:

Finding minimum area k-gons. D. Eppstein, M. Overmars, G. Rote, and G. Woeginger. Disc. Comp. Geom. 7(1):45-58, 1992. http://www.ics.uci.edu/~eppstein/pubs/EppOveRot-DCG-92.pdf

It says k-gon and area in the title rather than convex-hull-of-k-points and perimeter, but it treats those variants as well. I have some later papers that handle cases when k is small more efficiently, but I think they're less relevant because here it seems that k could well be large.

MiP said...

Thanks for the link, David! The k in your paper is what I call n-k, and in the regime of this problem it is Omega(n). So your algorithm would be O(n^4). On first look, it seems another factor of n is needed to search for the correct k, but maybe something cheaper can be done...

The best solution I know (in terms of my definition, k=#trees you cut) is O(n^2 + n*k^4).

D. Eppstein said...

The factor needed to search for the correct k is only logarithmic (binary search), but I think with the approach from my paper it vanishes altogether (just do the big dynamic program once and for all). So the time would be just O(n^4).

If you are looking for techniques that transform some of that dependence on n into a dependence on (your) k, expecting k to be small, you might try looking at Matoušek's "On Geometric Optimization With Few Violated Constraints".

Anonymous said...

Ha. But there is an easy approximation algorithm that would work in O(n + (k/eps)^O(1)) and would output a convex polygon wit parimeter (1+eps) the optimal one ignoring k points.

And the LP with violations would not work here, I think, since convex hulls have unbounded VC dimension.