"The book of nature is written in the characters of geometry."

Galileo
Go to Specific
Links
Related to COMP507 (Computational Geometry course).
General
Links  Computational
Geometry:
General Links  More Geometry:
Specific
Links Related to the Course Material:
Chapter
Links:
 Classical
Geometry, Basic Concepts, Theorems and Proofs
 Point
Inclusion Problems
 Convexity
Testing
 Polygon
Triangulation
 ArtGallery
Theorems
 Polygonizations
of Point Sets and Generating Random Polygons
 Distances
Within and Between Sets
 Subdivisions
Induced by Points: Triangulations, Quadrangulations...
 Complexity,
Convexity and Unimodality
 Convex
Hulls
 Visibility
(HiddenLine Problems)
 Updating
Triangulations of Points and Line Segments
 Intersection
Problems
 Proximity
Graphs, Voronoi Diagrams and Polyhedral Computations
 Linear
Programming
 Facility
Location
 Mobility
of Objects in Space
 Degeneracies
in Computational Geometry
 Transversals
of Sets
 Arrangements
 Skeletons
of Polygons
 Visualization
1.
Classical
Geometry, Basic Concepts, Theorems and Proofs
 The StraightEdge and
Compass Computer:
 Francois
Labelle's Tutorial on the Complexity of Ruler and Compass Constructions
(with interactive Java applet)
 GRACE
(A graphical ruler and compass editor)
 The
straightedge and
compass
 Constructive
geometry of the Greeks
 Geometric
constructions
 Geometrography
and the Lemoine simplicity of geometric constructions
 Wonders
of Ancient Greek Geometry
 Models of Computation:
 Ceiling
and Floor functions
 Polygons
and representations
 Computing
the area of a polygon
 On Proving Things:
 Notes
on methods of proof
 100%
Mathematical Proof
 The
Nuts and Bolts of Proofs
 Writing
Down Proofs
 On
Proofs in Mathematics
 Imre
Lakatos on Proofs and Refutations
 More
about Imre Lakatos
 Common
errors in mathematics
2.
Point
Inclusion Problems
 The Jordan Curve
Theorem:
 Octavian
Cismasu's Tutorial on the Jordan Curve Theorem (with interactive
Java
applet)
 PointinPolygon Testing:
 The
plumbline algorithm
 More
on the plumbline algorithm
 Point inclusion in the query mode
 Convex Polygons:
 Testing
the orientation of a simple polygon
 Testing
the convexity of a polygon
 History
of Triangulation Algorithms
 Ears and Mouths of
Polygons:
 Ian
Garton's
Tutorial on cutting ears and stuffing mouths (with interactive Java
applets)
 Simple
polygons have ears
and mouths
 Meisters'
TwoEars
Theorem
 More
about Gary
Meisters
 The onemouth theorem:
 Ian
Garton's Tutorial
 Polygons
are Anthropomorphic
(PostScript file)
 Diagonal insertion
 PruneandSearch:
 Finding
an
ear in linear
time (PostScript)
 Finding
an ear
in linear time (HTML)
 The
Graham
Scan
triangulates simple polygons (PostScript)
 Fast
Polygon Triangulation in Practice:
 Efficient
polygon
triangulation algorithms. Includes counterexamples
to many published algorithms. (PostScript)
 Geometric
hashing for faster EarCutting in practice (PostScript)
 Seidel's
Algorithm
 Triangulating
monotone polygons in linear time
 Diagonals:
Part I  AMS Feature Column Essay by Joseph Malkevitch
 The ArtGallery
problem:
 Chvatal's
art gallery theorem
 Thierry
Dagnino's Tutorial on Chvatal's artgallery theorem (with
interactive
Java applet)
 Threecolorability of
triangulated
polygons
 Illuminating
the Free Space Among Quadrilateral Obstacles
 Mobile
(edge) guards
 Illuninating
polygons with mirrored walls
6.
Polygonizations of Point Sets and Generating Random Polygons
 Drawing Simple
Polygons
through
Sets of Points:
 Tony
Ruso & Valeriu Sitaru's Polygonization Tutorial (with
interactive
Java applet)
 Monotonic
polygonizations
 Starshaped
polygonizations
 Polygonization
counter (Java applet)
 Generating
Random Polygons
 Midpoint
Polygonization of Points (with Java applet)
7.
Distances
Within and Between Sets
 Minkowski
metrics
 Distance
 Manhattan
metric: Pascal Tesson's tutorial on taxicab geometry
 Minkowski Operations:
 Minkowski
sum and difference
 Software
for computing Minkowski sums
 More
about Hermann Minkowski
 The Closest Pair
Problem:
 Closestpair
applet animation of divideandconquer algorithm
 Diameter algorithms:
 Diameter
algorithms (Mathew Suderman's tutorial)
 Computing the Width of
a
Set:
 Jaqueline
Chen's tutorial on width (with interactive Java applet)
 Width
algorithms in
2 and 3 dimensions (PostScript file)
 The
Rotating
Calipers
 The Rotating
Caliper Page of Hormoz Pirzadeh (with an awsome
Java applet!)
 Solving
five geometry problems with the rotating calipers
 The
Rotating Caliper Graph
 The
Reuleaux triangle (Eric's Treasure Trove)
 The
Reuleaux triangle (The Geometry Junkyard)
 Shapes
of Constant Width
 The Maximum Distance:
 A
simple
O(n log
n) algorithm for computing the maximum distance between two finite sets
in the plane (PostScript)
 A
more
complicated
O(n log n) algorithm for the maximum distance between two point sets
which
generalizes to higher dimensions (PostScript)
 The Minimum Distance:
 The
minimum distance
between two point sets (PostScript)
 The
minimum
vertex distance between two convex polygons (PostScript)
 The Hausdorff Distance:
 The
Hausdorff Distance
 Normand
Gregoire
& Mikael Bouillot's Tutorial on the Hausdorff distance and its
applications (with
interactive Java applet)
8.
Subdivisions
Induced by Points: Triangulations, Quadrangulations...
 Triangulations:
 Triangles
 Triangulation via Polygonizations of points
 Divideandconquer
 The threecoins algorithm
 Monotone polygons
 Starshaped polygons
 Edgevisible polygons
 Externally visible polygons
 MinimumWeight
Triangulations:
 Francois
Labelle's interactive Java applet
 Minimumweight
triangulation of a convex polygon
 Quadrangulations:
 Quadrilaterals
 Martin
Blais' Tutorial on Quadrangulations (with interactive Java applet)
 Characterizing
and Computing
Quadrangulations of point sets (PostScript file)
 Converting
triangulations
to quadrangulations (PostScript file)
 Application
of convex quadrangulations to font design
9.
Complexity,
Convexity and Unimodality
 Convex
Set, convex function
 Unimodal distance
functions
in geometry
 Binary Search
 Convex
hull algorithms for points in the plane (Java interactive demos)
 Convex
hulls in 2 and 3 dimensions (interactive Java demos)
 Incremental
(pointinsertion)
 Randomized
incremental (PostScript)
 The
Graham scan
 More about Ron
Graham
 Divide
& Conquer (merge hull)
 Quickhull
(throwaway principle)
 The
Jarvis march (giftwrapping)
 Chan's
Algorithm
 More
about Timothy Chan
 KirkpatrickSeidel's
ultimate algorithm (PostScript)
 More
about David Kirkpatrick
 Qhull
Home Page
 Convex
hulls and duality
 Linear expected time
algorithms
 Via BucketSorting
and Floor Functions (compressed PostScript file)
 The
throwaway principle (PostScript)
 A
fast convex hull algorithm  Algorithm of Akl and Toussaint (PDF
file)
 Convex hull algorithms
for
polygons:
 3Coins
Algorithm Tutorial (Greg Aloupis and Bohdan Kaluzny)
 Melkman's
lineartime algorithm (Pierre Lang's tutorial with Java applet)
 Another
tutorial on Melkman's algorithm
 A
History of Lineartime Convex Hull Algorithms for Simple Polygons 
by Greg Aloupis
11.
Visibility
(HiddenLine Problems)
 Visibility from a point
 Visibility
from an edge (PostScript)
 Visibility from a line
 Visibility Graphs
 Computing
visibility graphs of line segments and polygons
12.
Updating
Triangulations of Points and Line Segments
 Updating
Triangulations:
 Sergei
Sauchenko's Tutorial on inserting and deleting vertices and edges
from
triangulations (with interactive Java applets)
13.
Intersection
Problems
 Intersecting convex
polygons:
 Slab method of Shamos
and
Hoey
 More
about Michael Shamos
 Eric
Plante's Tutorial on the RotatingCaliper method (with interactive
Java applet)
 A
simple linear algorithm for intersecting convex polygons (Rotating
Caliper
method) (PostScript file)
 Intersecting halfplanes
 Intersecting simple
polygons
 Applications
 Linear Programming
 Voronoi diagrams
 Kernel of a polygon
14.
Proximity
Graphs, Voronoi Diagrams and Polyhedral Computations
 Minimum
spanning trees
 Nearest neighbour graphs
 The
Relative Neighbourhood Graph (PostScript)
 Lune
(also vescica piscis
or lens)
 The Gabriel graph
 The Delaunay triangulation
 Delaunay
Triangulations for Spatial Modelling
 Finding
2D Delaunay Trinagulations from 3D Convex Hulls (interactive Java
applet)
 Comparison
of Delaunay TrinagulationAlgorithms
 Computing
Constrained Delaunay Trinagulations in the Plane
 Voronoi Diagrams:
 The
Voronoi Web Site (Christopher Gold)
 VoroGlide
(fantastic interactive Java applet for Voronoi diagrams and Delaunay
triangulations)
 Another
interactive applet for delaunay triangulations and Voronoi diagrams
 A
Voronoi vertex is the circumcenter of its Delaunay triangle
 David
Eppstein's Links for Voronoi diagrams and applications
 Voronoi
Implementation (great applets!!!)
 Tutorial
on Fortune's Voronoi Diagram Algorithm
 HigherOrder
Voronoi Diagram Applet
 Applications of
Voronoi
Diagrams:
 Mark
Grundland's Fractals from Voronoi diagrams
 Sphere of influence
graphs
(SIG's)
 Richard
Unger's tutorial on SIG's (with interactive Java applet)
 Proximity
Graphs (including a survey paper)
 Alpha Shapes and Beta
Skeletons:
 Alpha
shapes
 François
Bélair's
Tutorial on Alpha Shapes (with interactive Java applet and a superduper
automated guidedtour demo)
 Gallery
of alpha shapes
 Code
for computing alphashapes (and convex hulls)
 Beta skeletons:
 Xiaoming
Zhong's Tutorial on Beta Skeletons (with interactive Java applet)
 Polyhedral Computation:
 Frequently
Asked Questions in Polyhedral Computation (by Komei Fukuda)
 What
is Linear Programming?
 Introduction
to Linear Programming
 Interactive
Linear Programming
 The
Simplex Algorithm (Java Applet)
 Linear programming
problems
in geometry
 Megiddo's linear time
algorithm
 Geometric
Series
 PruneandSearch
Algorithm Applet
 The minimax facility
location
problem
 The smallest enclosing
circle:
 An
O(n log n) algorithm (with interactive Java applet)
 Smallest
Enclosing Ball Code
 C++
Code for Smallest Enclosing Balls in all Dimensions
 The
linear time algorithm of Megiddo and Dyer (Tutorial of Jacob Eliosoff
and
Richard Unger with applet)
 Generalizations to
geodesic
metrics
 Constrained facility
location
problems
in the plane and on the sphere
 A
survey of geometric facility location problems
17.
Mobility
of Objects in Space
 The
MatchStick Game: Fabienne Lathuliere's Tutorial on Translation
Separability
of Sets of Line Segments (with interactive Java applet)
 Translation
separability of objects (compressed PostScript file)
 Separating
objects in space (Tutorial by Kishore
Anand and Anatoly Lichatchev with EXPLOSIVE
applet!)interactive 4bar linkage applet
 The
Rhombic Dodecahedron
 Separating
Two Monotone Polygons in Linear Time
 Separating
Two Simple Polygons via Relative Convex Hulls
 Geodesic Paths:
 Geodesic (relative)
convex
hulls
 Steve
Robbins' Tutorial on Relative Convex Hulls
 Shortestpaths
for robotics planning (with Java applet)
 The algorithm of
Chazelle
and LeePreparata
 Linkages
 A
historical introduction to linkages by Joseph Malkevitch
 Interactive
4bar linkage applet
 Planar
Machines' web site. An invitation to Topology. (multiple link
linkages!
fantastic site!!!)
 Paucellier's
Linkage
 Convexifying Polygons:
 Linda
Sun's tutorial on generating selfavoiding polygons
18.
Degeneracies
in Computational Geometry
 General
position assumptions
 What
is a degeneracy?
 Some
examples of geometric degeneracies
 Robustness
 An
arithmetic for handling intrinsic degeneracies
 Lower
bounds for detecting affine and spherical degeneracies
 Avoiding
AlgorithmInduced Degeneracies: (PostScript)
 No two points on a
vertical
line
 No three points on a
vertical plane
 No two points with the
same
coordinates
 and many many more
 Computing
nice viewpoints of objects in space (PostScript)
19.
Transversals
of Sets
 The Philo Line (Philo
of
Byzantium):
 Definition
and computation
 Historical
survey and characterizations
 Pointline duality:
 Interactive
Java demos illustrating various definitions of duality
 The space of transversals
 Computing
shortest transversals
20.
Arrangements
 Arrangements of lines
 Envelopes
of Arrangements of Lines (compressed PostScript file)
 Arrangements of line
segments
 Arrangements of discs
 Arrangements
of Jordan curves
21.
Skeletons
of Polygons
 The
medial axis
 The
StraightLine skeleton
22.
Visualization
 Nice Projections:
 Map
projections
 Regular
Projections and Knot Theory
 ApertureAngle
Optimization Problems:
 Viewing
a statue
 Applet
for aperture angle demo
 The
Spindle Torus
 Kepler's Apples and
Lemons
 More
about Kepler
 Apertureangle
optimization problems in two dimensions (PostScript)
 Apertureangle
optimization problems in three dimensions (PostScript)