README: PTW, the Pseudo-Triangulation Workbench, and other tools
======================================================================


Home Page:   http://www.cs.unc.edu/~kettner/proj/PseudoT/
----------


Introduction:
-------------

The Pseudo-Triangulation Workbench (ptw) is a research tool to
investigate pseudo-triangulations of points in the plane. It allows to
create point sets, compute pseudo-triangulations using various algorithms,
interact with them using flips, highlight interesting properties using
different color schemes, and enumerate all pseudo-triangulations for a
given point set. The enumeration can also be used with a branch&bound
version to test hypothesis, such as minimal vertex degree. Currently,
the algorithms and enumeration for pseudo-triangulations create only
minimal pseudo-triangulations.  Some support exists for normal
triangulations as well, such as creation and diagonal flips.

I was writing most of this program during the January 2001 Workshop
on Pseudo-Triangulations in Barbados. I spend around 25 hours during the
workshop and another 25 hours after the workshop on implementing and
documenting this prototype. It is based on my halfedge data-structure
released with CGAL 2.3, see www.cgal.org. It uses CGAL for the geometry,
OpenGL for the graphics, and GLUT with GLUI for the window GUI surface.

Later, I developed the additional command-line tools for enumerating
pseudo-triangulations and applied them to the data base of all order
types of small point sets in the plane to up to ten points, see [1].
I was able to compute the number of pseudo-triangulations for up to
and including nine points. Ten points are expected but not ready yet.

[1] O. Aichholzer and F. Aurenhammer and H. Krasser
    Enumerating Order Types for Small Point Sets with Applications
    In Proc. 17th Ann. ACM Symp. Computational Geometry, Medford,
    Massachusetts, USA, 2001.
    http://www.igi.TUGraz.at/oaich/triangulations/ordertypes.html


Documentation:
--------------

See the Copyright file for copyright and license regulation.

See the INSTALL file for installation instructions.

See ptw/doc/userman.ps.gz for a User Manual for PTW. 

The command-line tools count_pseudo_triang, diff_pseudo, eval_pseudo,
and extract_pseudo_triang print a small usage message when called with
the -h option. However, they work with the order type data base placed
in the local subdirectory ./data/ and they use the data base naming scheme
to distinguish 8/16/32 bit binary data. Please read to the source of 
these tools for the details (the sources are fairly short).


Disclaimer:
-----------

These programs are research prototypes! Especially ptw does not
provide a clean, homogeneous or foolproof user interfaces. It is easy
to bring it in an inconsistent state where answers of the system are
plain meaningless. However, I have not seen it crashing a lot. ;-)

The underlying geometry is not robust! The programs use currently
machine double arithmetic (could be changed easily but there is no
need as long as we work with input points distinguishable in the
graphics window or from the order type data base). It also does not
handle degeneracies, e.g., three points on a line. I have not spend
the time to have something for the definition of reflex vertex in 
that case.

The enumeration is supposed to enumerate all pseudo-triangulations for
a given set of points. Correctness of the implementation has been
validated with some example cases of wheels where we do know the exact
number. More confidence has been established with a second, independent
implementation of the same algorithm by Herve Broennimann that gives the
same answers for all point sets in the order type data base for up
to and including nine points.

Not scalable! This program is designed for interactive exploration.
Especially the interactivity and visualization are quite wasteful in
time assuming there will be only small to middle sized pseudo-
triangulations. However, several of the algorithms, the flip, and
especially the enumeration are efficient, and the enumeration has
undergone a first performance tuning.


Feedback:
---------

Comments, suggestions for extensions, and bug-reports are welcome. Please 
write me at kettner@cs.unc.edu.

Lutz Kettner
Dept. of Computer Science
University of North Carolina at Chapel Hill
USA