Paper by Erik D. Demaine

Stelian Ciurea, Erik D. Demaine, Corina E. Pǎtraşcu, and Mihai Pǎtraşcu, “Finding a Divisible Pair and a Good Wooden Fence”, in Proceedings of the 3rd International Conference on Fun with Algorithms (FUN 2004), Isola d'Elba, Italy, May 26–28, 2004, pages 206–219.

We consider two algorithmic problems arising in the lives of Yogi Bear and Ranger Smith. The first problem is the natural algorithmic version of a classic mathematical result: any (n + 1)-subset of {1, …, 2n} contains a pair of divisible numbers. How do we actually find such a pair? If the subset is given in the form of a bit vector, we give a RAM algorithm with an optimal running time of O(n / lg n). If the subset is accessible only through a membership oracle, we show a lower bound of (4/3) n − O(1) and an almost matching upper bound of (4/3 + 1/24) n + O(1) on the number of queries necessary in the worst case.

The second problem we study is a geometric optimization problem where the objective amusingly influences the constraints. Suppose you want to surround n trees at given coordinates by a wooden fence. However, you have no external wood supply, and must obtain wood by chopping down some of the trees. The goal is to cut down a minimum number of trees that can be built into a fence that surrounds the remaining trees. We obtain efficient polynomial-time algorithms for this problem.

We also describe an unusual data-structural view of the Nim game, leading to an intriguing open problem.

The paper is 12 pages.

The paper is available in PostScript (178k), gzipped PostScript (72k), and PDF (105k).
See information on file formats.
[Google Scholar search]

Related papers:
DivisiblePair_SIGSAM (Finding a Divisible Pair)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.