Paper by Erik D. Demaine

Reference:

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.

BibTeX

@InProceedings{Yogi_FUN2004,
  AUTHOR        = {Stelian Ciurea and Erik D. Demaine and
                   Corina E. P\v{a}tra\c{s}cu and Mihai P\v{a}tra\c{s}cu},
  TITLE         = {Finding a Divisible Pair and a Good Wooden Fence},
  BOOKTITLE     = {Proceedings of the 3rd International Conference on Fun with
                   Algorithms (FUN 2004)},
  bookurl       = {http://www.di.unipi.it/fun04/},
  MONTH         = {May 26--28},
  YEAR          = 2004,
  ADDRESS       = {Isola d'Elba, Italy},
  PAGES         = {206--219},

  papers        = {DivisiblePair_SIGSAM},
  length        = {12 pages},
  withstudent   = 1,
}

Abstract:

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.

Length:

The paper is 12 pages.

Availability:

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)