Personal tools
You are here: Home Events cgal-socg-2012 CGAL, an Open Gate to Computational Geometry
« September 2020 »
Log in

Forgot your password?

CGAL, an Open Gate to Computational Geometry


an Open Gate to Computational Geometry

June 18th, 2012, Chapel Hill, NC, USA
Part of CG-Week 2012


This year a series of mini-symposia, gathered under the collective title Computational Geometry: Applications, Practice, and Theory (CG:APT), will be co-located with the 28th Symposium
on Computational Geometry (SoCG)
. These mini-symposia together with SoCG will constitute the "CG-Week 2012". The aim of this mini-symposium is to provide a sample of  academic
projects that are based on CGAL but are not part of CGAL. The focus will be on excellent academic projects that, in total, will reflect the use of  computational geometry outside of our community.

The symposium consist of four invited talks and a poster session. We believe that the poster session is an excellent opportunity for CGAL users to present and demonstrate their work and
to receive invaluable feedback from their peers in an informal setting. Talks are of introductive nature, each addressing  the specific problem and the respective research field of a project
using CGAL. Speakers will also emphasize the links of their research field to computational geometry.


Call for Posters

CGAL users are invited to submit posters  to present and demonstrate their work. Posters will be reviewed by members of the CGAL Editorial Board based on originality, significance, quality,
and clarity. Applications should be submitted by email to Accepted posters are required to appear in the poster session as a printed document with format DIN A1.
The full text of the call for posters can be found here.


Important Dates
May 20th, 2012 Deadline for submissions 
May 27th, 2012
Notification of acceptance
June 18th, 2012 Mini-symposium

Program (preliminary, time schedule of SoCG not fixed yet)



Monique Teillaud
A short Introduction to CGAL (pdf)


Alexander Kroeller

Braunschweig Institute of Technology

Applied Art Gallery Problems -- CGAL meets CPLEX (pdf)

The classical Art Gallery Problem asks for the minimum number of guards that
achieve visibility coverage of a given polygon. It is known to be NP-hard, even
for very restricted and discrete special cases. Even though the it has been
extensively studied in almost 40 years, practical algorithms to find optimal
solutions or almost-optimal bounds are not known. We present a primal-dual
algorithm based on linear programming that provides lower bounds on the
necessary number of guards and—in case of convergence and integrality—ends
with an optimal solution. It has been implemented and extensively tested on
different classes of polygons; experimental results will be discussed. Additionally
we show how to extend the procedure to practical applications of the Art Gallery
Problem. These occur in laser scanning of buildings, but come with additional
properties—such as limited viewing range and loss in quality over distances.

Joint work with Tobias Baumgartner, Sándor P. Fekete, Mahdi Moeini, and Christiane Schmidt.

Rien van de Weijgaert

Kapteyn Institute, University of Groningen

Alphashapes and the Topology of the Megaparsec Universe (pptx, movie)

Over the past decades a clear paradigm has emerged as large redshift surveys
opened the window onto the distribution of matter in our Local Universe: galaxies,
intergalactic gas and dark matter exist in a wispy weblike spatial arrangement
consisting of dense compact clusters,  elongated filaments, and sheetlike walls,
amidst large near-empty void regions. The Cosmic Web is the fundamental spatial
organization of matter on scales of a few up to a hundred Megaparsec, scales at
which the Universe still resides in a state of moderate dynamical evolution.

While the complex intricate structure of the cosmic web contains a wealth of
cosmological information, its quantification has remained a major challenge.
In this lecture, we describe our effort to measure key topological parameters.
To this end, we resort to the homology of the weblike structure, and determine
the scale-dependent Betti numbers. For 3-D structures they count the number
of components, tunnels and enclosed voids. Out study includes a study of
persistence and persistent homology, which entails the conceptual framework
for separating scales of a spatial structure. To infer this from the discrete spatial
galaxy distribution (or of particles in computer models of cosmic structure formation)
we extract the homology from alpha shapes. Alphashapes were introduced by
Edelsbrunner to formalize the concept of "shape" for a spatial point dataset.
At large value of alpha corresponds to the convex hull of the dataset, while as
alpha shrinks the alphashape assumes cavities which may join to form tunnels
and voids.

We have studied the alpha complex of the cosmic weblike point patterns, in
order to assess the signature of filaments, walls and voids. The physical
interpretation of the obtained scale-dependence of Betti numbers is determined
from a range of cellular point distributions. The findings from the Voronoi
clustering models is used to analyze the outcome of cosmological N-body
simulations and the SDSS galaxy redshift survey.

Joint work with G. Vegter, H. Edelsbrunner, B.J.T. Jones, P. Pranav, C. Park, W.A. Hellwing,
B. Eldering, N. Kruithof, E.G.P. Bos, J. Hidding, J. Feldbrugge, E. ten have, M. van Engelen, M. Caroli, M. Teillaud.

Fast Forward for Poster Session


Coffee Break / Poster Session


Jeff Martin

Duke University

Geometric Arrangement Algorithms for Protein Structure Determination (pdf)

Nuclear magnetic resonance (NMR) spectroscopy is a primary tool to
perform structural studies of proteins in physiologically-relevant
solution conditions. Restraints on distances between pairs of protons
in the protein, derived from the nuclear Overhauser effect (NOE),
provide information about the structure of the protein in its folded
state. Ambiguity in the proton assignments for the NOEs render these
geometric constraints uncertain, hence complicating the determination
of an atomic-resolution structure. In cases where this uncertainty is
unable to be resolved experimentally, computational approaches are
needed, but traditional solutions often rely on stochastic search
coupled with simulation, which has many tunable parameters that must
be chosen carefully and can potentially miss structures consistent
with the experimental restraints. We reduce the structure
determination of protein homo-oligomers with cyclic symmetry to
computing geometric arrangements of unions of annuli in a plane. Our
algorithm, DISCO, runs in expected O(n^2) time, where n is the number
of distance restraints, allowing for ambiguous assignments.
Furthermore, DISCO guarantees to report all oligomeric structures
consistent with the experimental restraints. DISCO's implementation
uses the arrangements package in CGAL and is freely available as open
source software.

Joint work with Bruce Randall Donald.

Ioannis Emiris

National Kapodistrian University of Athens

Constructing Resultant Polytopes by a Vertex Oracle (pdf)

We develop a new paradigm to construct polytopes whose vertices can
be obtained by an effective oracle in a unique fashion. Starting with the
Newton polytope of the resultant, our method also efficiently computes
secondary polytopes as well as the Newton polytope of the discriminant
as a Minkowski sum. Our algorithm requires the minimum number of
oracles, each reducing to a constant number of regular triangulations
of the input pointset. Our software is based on the CGAL experimental
package "triangulation" and has allowed us to compute  resultant
polytopes in 7 or 8 dimensions. It has also yielded the most complex
3d (figure) and 4d resultant polytopes, the latter with f-vector
(22,66,66,22,1), thus opening the study of this polytope family.



Michael Hemmer Tel Aviv University
Mariette Yvinec INRIA Sophia Antipolis - Méditerranée
Document Actions