CGAL, an Open Gate to Computational Geometry
an Open Gate to Computational GeometryMinisymposium

This year a series of minisymposia, gathered under
the collective title Computational Geometry: Applications, Practice, and
Theory (CG:APT), will be colocated with the 28th Symposium on Computational Geometry (SoCG). These minisymposia together with SoCG will constitute the "CGWeek 2012". The aim of this minisymposium 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 cgalsocg2012@inria.fr. 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  Minisymposium 
Program (preliminary, time schedule of SoCG not fixed yet)
14:2014:40 
Monique Teillaud


14:4015:20 
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 NPhard, 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 almostoptimal bounds are not known. We present a primaldual 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. 

15:2016:00 
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 nearempty 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 scaledependent Betti numbers. For 3D 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 scaledependence 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 Nbody 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. 

16:0016:10 
Fast Forward for Poster Session 

16:1016:40 
Coffee Break / Poster Session 

16:4017:20 
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 physiologicallyrelevant 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 atomicresolution 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 homooligomers 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.


17:2018:00 
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 fvector (22,66,66,22,1), thus opening the study of this polytope family. 
Organizers 


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