CGAL, an Open Gate to Computational Geometry
an Open Gate to Computational Geometry
|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.
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 firstname.lastname@example.org. 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.
|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)
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
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
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
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
Joint work with Bruce Randall Donald.
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|