2000-09-18

Boustrophedonica

Definition:

From the Webster's II New Riverside University Dictionary:

bou*stro*phe*don (boo'stre-fed'n, -fe'don') n. [Gk. boustrophedon, turning like an ox while plowing: bous, ox + strephein, to turn.] An ancient writing method in which the lines were inscribed alternately from right to left and from left to right. -- bou*stroph'e*don'ic (-strofidon'ik) adj.

Examples:

  • Searching for a parking space in a very full parking lot. Question: At what fullness is this a good strategy vs. driving down a side looking to see an empty one (depends upon dimensions of lot, spacing of rows and spaces, etc.).
  • Searching for a word in a array of letters.
  • Browse-based shopping in a grocery store.
  • Any time a path must be continuous through a lattice doing work as much as possible.
  • Old line printers, like the Apple Imagewriter. Question: Do laser printers scan this way internally?

Non-examples:

  • Televisions. They only do `work' in the left-to-right direction, returning right-to-left without modifying the image. This could be called semiboustrophedonic, since useful work is done on half the traversals.
  • Any time the penalty for not doing return work is low. Two-dimensional computer array scans are easy to express semiboustrophedonically. For example (in C):
    for(i = 0; i < N; i++) {
       for(j = 0; j < M; j++) {
         a[j][i]++;
      }
    }