(Rice found four and a computer programmer named Richard James found one.) The list of families grew to 13 and, in 1985, to 14.
But soon after, lay readers like Marjorie Rice, a San Diego housewife with a high school math education, discovered new tessellating pentagon families beyond those known to Kershner. News of Kershner’s pentagon claim spread to the masses in 1975 when it appeared in Martin Gardner’s popular math column in Scientific American. But Kershner’s paper left out the proof that his list was exhaustive “for the excellent reason,” reads an introductory note, “that a complete proof would require a rather large book.” Then, in 1968, Richard Kershner of Johns Hopkins University discovered three more types of tessellating convex pentagons and claimed to have proved that no others existed. Reinhardt didn’t know whether his five families completed the list, and progress stalled for 50 years.
In his 1918 doctoral thesis, the German mathematician Karl Reinhardt identified five types of irregular convex pentagons that tile the plane: They were families defined by common rules, such as “side a equals side b,” “ c equals d,” and “angles A and C both equal 90 degrees.”
But squash and stretch a pentagon into an irregular shape and tilings become possible. The ancient Greeks proved that the only regular polygons that tile are triangles, quadrilaterals and hexagons (as now seen on many a bathroom floor). Other quadrants have to be split further.Try placing regular pentagons - those with equal angles and sides - edge to edge and gaps soon form they do not tile. After the first split, the southeast quadrant is entirely green, and this is indicated by a green square at level two of the tree. To construct a quadtree, the field is successively split into four quadrants until all parts have only a single value. Figure: An 8 x8, three value raster (here, three colours) and its representation as a region quadtree. Therefore, a quadtree provides a nested tessellation: quadrants are only split if they have two or more different values. When a conglomerate of cells has the same value, they are represented together in the quadtree, provided their boundaries coincide with the predefined quadrant boundaries. Quadtrees are adaptive because they apply Tobler’s law. The links between them are pointers, i.e. a programming technique to address (or to point to) other records. In the computer’s main memory, the nodes of a quadtree (both circles and squares in the Figure) are represented as records. The procedure produces an upside-down, tree-like structure, hence the name “quadtree”. This procedure stops when all the cells in a quadrant have the same field value. The quadtree that represents this raster is constructed by repeatedly splitting up the area into four quadrants, which are called NW, NE, SE, SW for obvious reasons. It shows a small 8×8 raster with three possible field values: white, green and blue. A simple illustration is provided in the Figure above. It is based on a regular tessellation of square cells, but takes advantage of cases where neighbouring cells have the same field value, so that they can be represented together as one bigger cell. A well-known data structure in this family - upon which many more variations have been based - is the region quadtree.
0 kommentar(er)
