INSTRUCTIONS FOR TESSINVERT, version 123. 3/01/02. ------------------------------------ BRIEF DESCRIPTIONS OF FILES IN THIS DIRECTORY: a.cpp Raw C++ code for Dirichlet tessellation inversion (Algorithm A) a2.cpp Algorithm A'. b.cpp Algorithm B. b2.cpp Algorithm B'. c.cpp Algorithm C. c2.cpp Algorithm C'. adam.cpp Modified Adamatzky algorithm. tessinverta Compiled C++ module for Dirichlet tessellation inversion (Algorithm A) tessinverta2 Algorithm A', compiled. tessinvertb Algorithm B, compiled. tessinvertb2 Algorithm B', compiled. tessinvertc Algorithm C, compiled. tessinvertc2 Algorithm C', compiled. tessinvertadam Modified Adamatzky algorithm, compiled. maker.s R code for generating simulated points from a uniform distribution, then constructing the Dirichlet tessellation of those points. Running "maker.s" in R generates the files "realpts.txt" and "tess.txt". realpts.txt Text file containing the actual spots to be tessellated. tess.txt Text file containing a representation of the tessellation. scr Script that runs "maker.s" in R, then runs "tessinvertc2" on the resulting tessellation, and stores the result in a file called "out". aftermaker.s R code for reading "out" and plots the inverted tessellation. tessms.pdf PDF version of the manuscript "Inverting Dirichlet Tessellations" by Paik Schoenberg, Ferguson, and Li, submitted to The Computer Journal. tessms.tex Latex file used to generate "tessms.pdf". tfig1.pdf Figure 1 of "Inverting Dirichlet Tessellations". tfig2.pdf Figure 2 of "Inverting Dirichlet Tessellations". tfig3.pdf Figure 3 of"Inverting Dirichlet Tessellations". tfig4.pdf Figure 4 of "Inverting Dirichlet Tessellations". tfig5.pdf Figure 5 of "Inverting Dirichlet Tessellations". tfig6.pdf Figure 6 of"Inverting Dirichlet Tessellations". tfig7.pdf Figure 7 of "Inverting Dirichlet Tessellations". ------------------------------------ TO USE THESE FILES: The module "tessinvertc2" (and other tessinvert modules) and the script "scr" are for use on UNIX systems only. For Mac or PC, you will need to compile the .cpp files yourself. The simplest way to run "tessinvertc2" on UNIX is simply to download the above files (minimally "tessinvertc2" and "tess.txt"), and at the UNIX prompt simply enter the command tessinvertc2. The file c2.cpp is compiled using the UNIX command g++ c2.cpp -o tessinvertc2 The file "maker.s" may be used to generate your own Dirichlet tessellations in R, which can later be inverted. You will first need to install the program "R" and the library "tripack", which at present are freely available at http://cran.r-project.org . See the installation instructions there. With R properly installed, one may source the commands in "maker.s" to generate uniformly distributed spots and construct the resulting Dirichlet tessellation. You may edit the first line of "maker.s" to change the number of spots generated. The file "maker.s" may be sourced in R by various means. One way is, within R, to use the command source("maker.s") Another way is to use the UNIX command R < maker.s --save (The optional argument --nosave is also acceptable, but then re-running this command will generate exactly the same spots.) A third way is to run the script "scr", which not only runs "maker.s" but also runs "tessinvertc2", and saves the output of "tessinvert" in the file called "out". See "maker.s" for more information on how to make a Dirichlet tessellation and how to store it correctly so that it may be inverted by "tessinvert". The R code in "aftermaker.s" may be used to plot a picture of the tessellation. ------------------------------------ NOTES AND DEGENERACIES: 1) The R function "voronoi.mosaic" within the "tripack" library in R, which is used in "maker.s" run to create the Dirichlet tessellation, sometimes has bugs. These are especially prevalent when n is large, i.e. 1000 or more. The problem always seems to be that the function's output is not quite complete; for instance often there may be vertices in the tessellation that are given only one or two adjacent vertices: the other elements in the adjacency list are zeros. The program "tessinvert" detects this error and stops if it sees it. For tessellations of many thousands of spots, a quick and very dirty way around this problem is to simply fill in the zeros with other integers. Typically only a few of the resulting segments will be in error, and the inversion will approximate the original spots pretty well. A better solution is to use the a different tessellation construction program and coerce the results into the format shown in "tess.txt". (This format is described in "maker.s".) Also, be warned that voronoi.mosaic is very slow. For more than a few hundred spots, this function can really take a long time to run. A new R package called "deldir", also available from CRAN, may correct these problems (hopefully). 2) Degeneracies. In its present form, the function "tessinvert" requires that each vertex of the tessellation either have exactly three adjacent vertices, or else be a dummy vertex. (For a description of dummy vertices, see the paper "Inverting Dirichlet Tessellations" or see the file "maker.s".) If a vertex X in your tessellation has four or more adjacent vertices, one way to handle this is by storing X two or more times, as if storing distinct vertices; no problem arises if some of the adjacent vertices may appear twice. This is what is typically done by voronoi.mosaic, but one may also do this by hand. For instance, suppose there are 68 nondegenerate vertices in "tess.txt", that vertex #9 = (5.0, 6.0) is adjacent to vertices #11, 12, 33, and 52, and that "tess.txt" currently says vertex #9 is only adjacent to #11, 12, and 52. That is, currently line #9 says: 5.0 6.0 11 12 52 One should then edit "tess.txt", adding the line after line 68: 5.0 6.0 11 12 33 Be sure to also increase the total number of nondegenerate vertices (i.e. change the very first integer in "tess.txt" from 68 to 69). If the tessellation's cells are not convex, that problem is detected by "tessinvertc2" but the program keeps on running anyway.