Close this search box.

Applied Computational Geometry, Spring 2009

0368-4073, a.k.a. Applied Geometric Computing

Lecture: Monday 16:00–19:00, Schreiber 008

InstructorDan Halperin
Office hours: Monday 19:00–20:00, Schreiber 219

Help deskEfi Fogel,  Eric Berberich: Monday 15:00–16:00 @ ACG lab (Schreiber basement)
Teaching assistantGuy Zucker


Transforming geometric algorithms into effective computer programs is a difficult task. The last decade has seen significant progress in this area, some of which we will review in the course. We will discuss various issues in computational geometry, algorithmic and numerical, from a practical perspective, as well as applications of geometric algorithms in several domains.

The course will concentrate on the following topics:

  • Arrangements of curves and surfaces and their applications
  • Minkowski sums
  • Geometric rounding
  • Movable separability of sets and assembly planning

Other topics that will be covered, as time permits, include:

  • Delaunay triangulations and their relatives as modeling tools
  • The CGAL project and library (beyond arrangements and Minkowski sums)
  • Motion planning techniques in algorithmic robotics
  • Dynamic maintenance of large kinematic chains

The course is geared towards graduate students in computer science. Third-year undergrads are welcome.


Computational Geometry. Knowledge of C++ or willingness to learn the language


The final grade will be determined by a short multiple-choice exam, and mostly by homework assignments including one large-scale project. It is possible to work and submit the assignments in pairs.

The exam will be held on Tuesday, 30/6/09, between 9:00 and 11:00. For more information about the exam click here.




  • Assignment 1, due March 23rd  [pdf]
  • Assignment 2, due April 6th [pdf] [ NEW! Detailed tutorial for CGAL installation on windows ]
    CGAL version 3.4, 64 bit, (without QT4 support) is installed at /usr/local/lib/cgal_3.4-1_qt3. If you want to use it, set the environment variable CGAL_DIR:

         setenv CGAL_DIR /usr/local/lib/cgal_3.4-1_qt3/lib/CGAL

    and proceed as usual.

  • Assignment 3, due May 15th [pdf]  [hints for Ex. 3.3]
  • Assignment 4, due June 11th [pdf]
    • The pdf was updated on 21/05/09. The word “vertex” was replaced by the word “edge” in the line before the last.
    • The data-set archive was updated on 26/05/09 with additional data files.
    • The Gaussian-map section was updated on 02/06/09 with instructions for obtaining the point geometric embedding of a primal vertex that corresponds to a Gaussian-map face.
    • The Gaussian-map section was updated (yet again) on 03/06/09 with
      • additional instructions to compile code that constructs Minkowski sums based on the Gaussian-map method, and
      • instructions to eliminate coplanar facets of a polytope.
    • A patch for merge_coplanar_planes.hpp was added in 07/06/09. The patch enables computing the width of dodecahedron.wrl and iso_cube.wrl.

Course Summary

  • 02/03/09 Introduction [pdf file; up till slide 38], to be continued
  • 09/03/09 Introduction, continued (2 hour lesson, Purim)
  • 16/03/09 Gentle Introduction to CGAL [pdf]
  • 23/03/09 2D Arrangements [pdf]
  • 30/03/09 3D Arrangements [pdf] (we covered slides 1-23 in class)
  • 20/04/09 3D Arrangements, continued (up till slide 30);

Minkowski Sums, Preliminaries [pdf2D Minkowski sums, general polygonal

  • 27/04/09 3D Minkowski Sums of Convex Polyhedra (2 hour lesson)[pdf]
    • Minkowski sum construction via convex hull [cpp]
  • 04/05/09 3D Arrangements, completed (from slide 31);

Spherical arrangements and more (up till slide 7) [pdf]

  • 11/05/09 Minkowski sums, the general polygonal case (slides 1-19) [pdf]
  • 18/05/09 Minkowski sums, the general polygonal case (slides 20-end);

more on arrangements of atom spheres: depth order, vertical decomposition

  • 25/05/09 Geometric rounding (up till slide 44) [pdf]
  • 01/06/09 Geometric rounding, completed
  • 08/06/09 2D Voronoi diagrams via envelopes of surfaces in space [pdf]
  • 15/06/09 Movable separability and assembly planning [pdf]

Installing CGAL and related programs on Windows operating system

This page explains how to install CGAL 4.9 with Boost 1.59.0 and Qt5 5.7.1 on Windows 8 using Visual Studio 12 (2013) generating 64 bit binaries. The same procedure should apply to earlier versions of Windows.

Note that during the entire setup you need Internet connection!

Note that the installation requires significant disk space. Make sure to free enough disk space before the installation.

Instructions on adding Environment Variables in Windows are at the end.


IMPORTANT: make sure that you install everything in 64-bit.

  1. Visual Studio 12 Professional (recommended) or Express.
    Professional – Students can get a free version here
  2. Boost 1.59.0: here
  3. CMake 3.7.1
  4. CGAL 4.9.0
  5. Qt5 5.7.1
In parentheses are the paths on my computer.
1) Visual C++ 2013:
  •  If you use the offline version, choose to install Visual C++.
  •  Accept the license terms.
  •  You may select a custom installation (instead of full) and select only Visual C++ (unselect other features).
  •  You don’t need to install “SQL Server” & “Silverlight Runtime” although you may.
  •  There is a chance that it is recommended to reboot now.
2) Boost

Versions earlier than 1.55 used to include a binary installer. Such an installer is no longer available. However, the procedure is fairly simple. There are several ways to build boost; the following is referred to as “build from source”.

  • Open a command-line terminal, such as ‘cmd’.
  • Make the compiler known by running the following batch file:
c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\vcvars32.bat
  • Download the boost archive, unpack it to a target directory of your choice (e.g., C:\boost\boost_1_55_0), and change directory to target directory.
  • Run:
  • Then, build the static, shared, single and multi threaded boost libraries:
.\b2 link=static,shared threading=single,multi variant=debug,release
  • Make sure the subdirectory stage\lib\ has been populated with the compiled libraries (both .lib and .dll files).
3) CMake
  •  -Agree to the license.
  •  Check “Add CMake to the system PATH for all users”.
  • Check “create desktop icon”.
  •  Next, Next, Next.
  •  Finish
4) QT
  •  Agree to the license.
  •  Next, Next, Next, Install.
  •  Add QTDIR variable with the value C:\Qt\5.7.1 to the environment variables (if it’s not already there).
  •  Add <QT>\bin to the system PATH. (C:\Qt\5.7.1\bin)
4.1) QT Visual Studio 2013 addin:
  •  install the addin (Is it still necessary in VC 12?)
  •  CGAL installation will need to connect to the internet for GMP and MPFR.
  •  Be amazed by the splash screen.
  •  Agree to the license.
  •  Just choose the default: with GMP and MPFR, and with examples and demos.
  •  64-bit (for me).
  •  In the “Setting Environment Variables” screen, choose all users and make sure that CGAL_DIR is checked.
  •  Install.
  •  Add <CGAL_DIR >\auxiliary\gmp\lib to the system PATH. (C:\Program Files\CGAL-4.9\auxiliary\gmp\lib)
Now you need to compile CGAL
  •  Open CMake – cmake-gui (on the Desktop) – if you are using win7 make sure you open the program in administrator mode – right click on the icon and click on “run as administrator”.
  •  For both “Where is the source code” and “Where to build the binaries” specify the CGAL Installation folder (C:\Program Files\CGAL-4.9)
  •  Click Configure.
  •  Choose “Visual Studio 12 2013” and click “Finish”
  •  Click Generate
  •  A solution named CGAL was created in the directory.
  •  Compile ALL_BUILD project both in Debug and Release (ignore the compilation error in CGAL_imageIO).
  •  All CGAL libraries should be under the lib directory.
6) Sanity check (optional)
  •  Open CMake (cmake-gui, can be found on the desktop) – (for win7 users, use “Run as admin”)
  •  Choose “Where is the source code:” to be the Triangulation_2 demo directory under the CGAL installation. Namely, <CGAL>/demo/Triangulation_2 (C:\Program Files\CGAL-4.9/demo/Triangulation_2).
  •  Choose “Where to build the binaries:” to the same directory.
  •  Click Configure
  •  Click Generate
  •  Go to the directory (C:\Program Files\CGAL-4.9) and open the solution and compile. Run the Delaunay_triangulation project for check (in debug and release)
7) Customizing env – If you are not using CMake to create new VS projects
 Note: the following operations should be repeated for the Debug and Release modes
  •  Right-click on the selected project and select “Properties”.
   Go to C/C++ -> General . Add the following to “Additional Include Directories” (include)
   * include: <Boost> (C:\Program Files\boost\boost_1_59)
   * include: <CGAL>\include (C:\Program Files\CGAL-4.9\include)
   * include: <CGAL>\auxiliary\gmp\include (C:\Program Files\CGAL-4.9\auxiliary\gmp\include)
   * include: <QT>\include\Qt (C:\Qt\5.7.1\include\Qt)
   * include: <QT>\include\QtCore (C:\Qt\5.7.1\include\QtCore)
   * include: <QT>\include\QtGui (C:\Qt\5.7.1\include\QtGui)
  Go to Linker -> General. Add the following to “Additional Dependencies” (include)
   * library: <CGAL>\lib (C:\Program Files\CGAL-4.9\lib)
   * library: <QT>\lib (C:\Qt\5.7.1\lib)
   * library: <Boost>\lib (C:\Program Files\boost\boost_1_59\lib)
   * library: <CGAL>\auxiliary\gmp\lib (C:\Program Files\CGAL-4.9\auxiliary\gmp\lib)
For a specific project using CGAL you need to ignore the auto-link of gmp and mpfr. The names below are for Debug.
 – Linker -> Input
   * Add libgmp-10.lib and libmpfr-4.lib to “Additional Dependencies”
   * Add gmp-vc100-mt-gd.lib and mpfr-vc100-mt-gd.lib to “Ignore Specific Library” (gmp-vc100-mt.lib and mpfr-vc100-mt.lib in release mode).
For a specific project using QT:
 – Linker -> Input
   * Add qtmaind.lib, QtGuid4.lib, and QtCored4.lib to “Additional Dependencies” (qtmain.lib;QtCore4.lib;QtGui4.lib in release).
Important: In case that the compilation succeeds but the linker is unable to find cgal-related dlls (“the program can’t start because cgal-vc100-mt-gd-4.2.dl is missing”)
find these files in the CGAL directory and copy them either to the system32 folder of windows, or the folder of the visual studio project.
Try to compile this programs:
Hello CGAL:

Setting up PATH variable or other Environment variables on windows systems

    1. From the desktop, right-click My Computer and click properties.
    2. (on Vista/Win7/Win8 click Advanced system settings on the left side)
    3. In the System Properties window, click on the Advanced tab.
    4. In the Advanced section, click the Environment Variables button.
    5. Finally, in the Environment Variables window, highlight the path variable in the Systems Variable section and click edit. Add or modify the path lines with the paths you wish the computer to access. Each different directory is separated with a semicolon as shown below.C:\Program Files;C:\Winnt;C:\Winnt\System32

Yair Oz - Webcreator


Skip to content