Program - The Workshop will be held in the building Euler - Room E006
Mercredi 26 septembre |
| |
9h - 10h00 |
|
Welcome Coffee |
10h - 10h30 |
|
10h30 - 11h00 |
|
11h00 - 11h15 |
Break |
11h15 - 11h45 |
|
11h45 - 12h15 |
|
12h15 - 14h00 |
Lunch |
14h00 - 14h30 |
|
14h30 - 15h00 |
|
15h00 - 15h30 |
|
15h30 - 16h00 |
Coffee Break |
16h00 - 16h30 |
Julian M. Smith |
16h30 - 17h00 |
|
Julien Wintz |
|
|
|
| 17h00 - 19h00 |
|
Private ACS Board Meeting |
|
|
|
Pierre Alliez
Voronoi-based Variational Reconstruction for Unoriented Point Sets
Abstract :
We introduce an algorithm for reconstructing watertight surfaces
from unoriented point sets. Using the Voronoi diagram of the input
point set, we deduce a tensor field whose principal axes and
eccentricities locally represent respectively the most likely
direction of the normal to the surface, and the confidence in this
direction estimation. An implicit function is then computed by
solving a generalized eigenvalue problem such that its gradient is
most aligned with the principal axes of the tensor field, providing
a best-fitting isosurface reconstruction. Our implicit
function optimization provides resilience to noise, adjustable
fitting to the data, and controllable smoothness of the
reconstructed surface. Finally, the use of simplicial meshesand
(an)isotropic Laplace operators renders the numerical treatment
simple and robust.
Lionel Alberti
Planar curve topology computation through certified numerical computation.
Abstract :
Certified topology computations are usually based on "sweeping" methods that need unecessary computations and introduce irrelevant numerical and genericity problems.
The method we designed is based on subdivision techniques. It isolates the singularities of the curve using a bivariate polynomial solver and creates a partition of the plane that matches the geometry of the curve. The rapid focus on the topologically interesting points speeds up the algorithm. The smooth part is dealt with by classical optimized subdivision methods. The topology inside the isolating boxes for the singularities is recovered from what happens on the boundary by using topological degree computations. Because we need only look at what happens on the boundary of the boxes where there is no singularity, we can use fast certified numerical computations.
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn and Ron Wein.
Sweeping and Maintaing Two-Dimensional Arrangements on Surfaces: A First Step
Abstract:
We introduce a general framework for processing a set of curves
defined on a continuous two-dimensional parametric surface, while
sweeping the parameter space. We can handle planes, cylinders, spheres, tori, and surfaces homeomorphic to them. A major goal of our work is to maximize code reuse by generalizing the prevalent sweep-line paradigm and its implementation so that it can be employed on a large class of surfaces and curves embedded on them. We have realized our approach as a prototypical CGAL package.
We present experimental results for two concrete adaptations of the framework for: (i) arrangements of arcs of great circles embedded on a sphere, and (ii) arrangements of intersection curves between quadric
surfaces embedded on a quadric.
Frédéric Cazals, joint work with A. Parameswaran, Sylvain Pion.
Robust construction of the three-dimensional flow complex
Abstract:
The Delaunay triangulation and its dual the Voronoi diagram are
ubiquitous geometric complexes. From a topological standpoint, the connection has recently been made between these cell complexes and the
Morse theory of distance functions. In particular, in the generic
setting, algorithms have been proposed to compute the flow complex
---the stable and unstable manifolds associated to the critical points
of the distance function to a point set. As algorithms ignoring
degenerate cases and numerical issues are bound to fail on general
inputs, this talk will discuss the first complete and robust algorithm
to compute the flow complex.
First, we present complete algorithms for flowing across Voronoi edges
and facets, unraveling a delicate interplay between the degenerate
cases of Delaunay and those which are flow specific.
Second, we explain how stable and unstable manifolds can be constructed from these, avoiding dedicated algorithms as done
previously. Third, we discuss numerical issues related to predicates on cascaded constructions. Finally, we report experimental results
with CGAL's filtered kernel, showing that the construction of the flow
complex incurs a small overhead wrt the Delaunay triangulation when
moderate cascading occurs. These observations provide important
insights on the relevance of the flow complex for (surface)
reconstruction and medial axis approximation, and should foster flow
complex based algorithms.
Stéphane Chau
Computing the topology of 4d implicit curves by using a subdivision method.
Abstract:
In Computer Aided Geometric Design (CAGD), the parameterized surfaces
are used delimiting volumes. The computation of the intersection curve
between such two surfaces is thus crucial for the description of the
CAGD objects. An often used method to address this problem consist in
using a mesh for each surface, and then to proceed to their
intersection (intersection of triangles).
Other methods for the intersection problem deal with global representations of the surfaces such as B-splines, however the usual CAGD procedures (offsetting, drafting, ...) do not conserve this model and procedural surfaces that are based on approximations are required. So, even if the intersection methods are exact, they only provide an approximation of the "real" intersection curve.
This can be of bad quality, because the approximations of the surfaces are separated from the intersection process and are somehow "global''. In the general case, the only informations that we can access for a parameterized surface are "local" (its evaluation). Thus, a general algorithm is a sampling algorithm like the mesh representation. If we use shapes more complex than the triangles, then the quality of the surfaces approximation will be better and thus the intersection locus too. For example, we can use Bézier surface patches of small degree. But if we want to use this kind of representation, we have to intersect efficiently such two polynomial prameterized surfaces. In this talk, we deal with this problem. This work presents a subdivision method in order to compute the topology of a four dimension implicit curve. This approach is efficient and avoid some drawbacks that appear in projection methods which are used by many authors.
Frédéric Edoukou
Error-Correcting Codes Constructed From Algebraic Varieties
Abstract
We study the functional code defined on a projective algebraic
variety X on a finite field, as this has been done by V. Goppa on algebraic
curves. The minimum distance of this code is determined by computing the
number of rational points of the intersection of X with all the hypersurfaces
of a given degree. In the case where X is a non-degenerate hermitian sur-
face, A.B. Sorensen has formulated a conjecture in his Ph.D thesis (1991),
which should give the exact value of the minimum distance of this code.
In this talk, we give a proof of Sorensen's conjecture for quadratic surfaces.
By using some results of finite geometries we give the weight distribution
associated to this code. We will study also the functional code of order 2
defined on quadratic surfaces and will show that for the ones built on ellip
tic quadratic surfaces according to their parameters, their are good codes.
We will give the best upper bounds for the number of points of quadratic
section of quadric varieties, and non-degenerate hermitian variety, in projective dimension 4. Finally we will propose a generalisation of the studied
conjecture for higher dimensional varieties.
Ioannis Emiris
Computational geometry in sparse elimination
Abstract :
This talk reviews some basic concepts of sparse, or toric, algebraic
elimination theory and emphasize problems that are related to or
generalize questions encountered in computational geometry. In
particular, we discuss convex polytopes and projections of such,
Minkowski sums and mixed subdivisions, regular triangulations and
secondary polytopes.
Bernd Gaertner
Approximate smallest enclosing ellipsoids in CGAL
Abstract :
The smallest ellipsoid containing a point set in d-dimensional space
(also known as the Loewner-John ellipsoid) is a very attractive
bounding volume, since it approximates the shape of the point set
well. This sets ellipsoids apart from other simple bounding volumes
like balls or boxes. Unfortunately, for d > 2, no algorithm is known
that can efficiently compute the exact smallest enclosing ellipsoid
of a given point set. The reason is that the coefficients of this
ellipsoid are in general algebraic numbers of high degree.
In practice, it is usually enough to approximate the Loewner-John
ellipsoid up to a given accuracy, and for this problem, Khachyian
gave an efficient algorithm.
In this talk, I survey Khachyian's algorithm and describe a robust
CGAL implementation of it. This implementation lets the user specify
the desired accuracy eps. The output is an ellipsoid and an accuracy
eps' (which is usually at most eps, but it can also be slightly
larger) such that the returned ellipsoid is guaranteed to be a
(1+eps')-approximation of the true Loewner-John ellipsoid.
Laureano Gonzalez-Vega, D.A. Aruliah, Rob Corless, Mario Fioravanti, Azar Shakoori
Offsets of real algebraic plane curves: topology and extraneous components.
Abstract :
Offsets of curves and surfaces appear very often in Computer Aided Geometric Design. Even if the initial curve or surface is rational, in general, the resulting offset is not rational but algebraic with a usually huge implicit equation. It is shown how to use the defining equations of the points on the offset to a real algebraic plane curve to determine its topology and the so called geometric extraneous components. These points need to be known in advance in order to use properly algebraic tools for solving intersection problems with the offset of the considered curve.
Michael Kerber, joint work with Arno Eigenwillig
Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves
Abstract:
We show how to compute the planar arrangement induced by segments
of arbitrary algebraic curves with the Bentley-Ottmann sweep-line
algorithm. The necessary geometric primitives reduce to cylindrical
algebraic decompositions of the plane for one or two curves.
We compute them by a new and efficient method that combines
adaptive-precision root finding (the Bitstream Descartes method of
Eigenwillig et~al.,\ 2005) with a small number of symbolic
computations, and that delivers the exact result in all cases.
Thus we obtain an algorithm which produces the mathematically true
arrangement, undistorted by rounding error, for any set of input
segments.
Our algorithm is implemented in the EXACUS library AlciX.
We report on experiments; they indicate the efficiency of our approach.
Daniel Lazard
Cell decomposition: a promising data structure for semi-algebraic sets.
Abstract:
A semi-algebraic cell (SAC) is an oriented semi-algebraic set which is isomorphic to the affine space R^k. A cell decomposition of a semi-algebraic set is a disjoint decomposition into SAC's such that each cell which intersects the border of another cell is included in it. A cell decomposition is effective if, for every cell, one knows an isomorphism onto an open subset of R^k and the list of the signed cells in its border is known, the sign indicating if the orientations are the same or not. An effective chain decomposition is, especially, a chain complex, and allows to known completely the topology of the semi-algebraic set.
Computing a SAC decomposition of an arbitrary semi-algebraic set is theoretically feasible but is, in practice, an open problem. On the other hand, most operations of algorithmic geometry are easier on semi-algebraic sets effectively decomposed into cells.
This allows to hope to devise practical algorithms for arrangement, convex hull, Voronoi diagram, ... of any number of semi-algebraic objects of low degree, under the condition that the the same problem is solved for 3 or 4 objects (in 3D space).
Sylvain Lazard, Luis Penaranda
A CGAL algebraic kernel based on RS and applications to arrangements of
polynomial functions.
Abstract:
The aim of this work is to validate the use of algebraic tools in computational
geometry and, in particular, for computing arrangements of algebraic curves.
We focus here on the case of curves defined by polynomial univariate functions.
More specifically, we describe an implementation of a CGAL algebraic
kernel using the RS software for isolation of univariate polynomials. We then explain
how this kernel is used with the CGAL arrangement package and show
some benchmarks to demonstrate the effectiveness of this approach.
Sylvain Lazard,
Luis Penaranda,
Marc Pouget, Fabrice Rouillier,
Elias Tsigaridas
Real Algebraic Plane Curve Topology and Geometry
Abstract:
The problem addressed is the analysis of a real algebraic
plane curve. Its topology is of prime interest, but in addition some
geometric information is relevant such that the position of special
points: singular or critical points. A difficulty is to compute this
information for the given coordinate system even if the curve is not
in generic position. In addition, costly computations with
polynomials with algebraic coefficients should be avoided, if
possible in all the cases.
An algorithm is presented that overcome these difficulties. The novelty of this algorithm relies upon the combination of (1) a formula of Teissier relating univariate multipicities in fibers and multiplicities in bivariate systems, and (2) the Rational Univariate Representation (RUR) of the solutions of bivariate system to isolate and compute the required multiplicities. It is worth mentioning that this approach avoids computations of subresultant sequences in all the cases.
Frédéric Cazals, Sébastien Loriot, Pedro M.M. de Castro, Monique Teillaud.
Design of the CGAL 3D spherical kernel, and application to arrangements
of circles on a sphere
Abstract:
This talk presents a new CGAL kernel for algorithms manipulating 3D spheres,
circles, and circle arcs. The talk presents three contributions.
First, the design of the concept is developed, following
the global kernel design introduced by Emiris et al. for curved objects.
Second, we present a two parts implementation, one for the general setting,
and one dedicated to the case where all the objects handled are located on
a reference sphere. In both cases, the mathematical derivations for predicates
and constructions are detailed. Finally, an application to the construction of
the exact arrangement of circles on a sphere is given.
Dan Halperin, Ophir Setter, Micha Sharir
Exact and Efficient Construction of General Voronoi
Diagrams in the Plane via Divide and Conquer of Envelopes
in Space
Abstract:
We present a general framework for implementing
Voronoi diagrams of convex sites of constant
description complexity in the plane under various
distance functions. The computation of the diagrams employs
the CGAL software for constructing the envelopes of
surfaces in 3-space, which implements a divide-and-conquer
algorithm. A straightforward usage of the
divide-and-conquer approach for Voronoi diagrams yields near-quadratic time algorithms in the worst case.
We show that through randomization, the
expected running time is only near-linear. We describe the
interface between the construction of the diagrams and the
underlying construction of the envelopes, together with
means we have applied to speed up the computation. We then
present experimental results obtained with our
implementation of a variety of diagrams including power
diagrams, Apollonius diagrams, anisotropic diagrams,
diagrams of line segments, and more.
Günter Rote
Adaptive intersection of splines.
Abstract:
We present a subdivision algorithm for computing the intersection of spline curves. The complexity depends on geometric quantities that represent the hardness of the computation in a natural way, like the angle of the intersection. The main idea is the application of the super-composition technique, which considers unions of adjacent parameter intervals that are not siblings in the subdivision tree. This approach addresses the common difficulty of non-termination of the classical subdivision approach when the intersection coincides with a subdivision point, but it avoids the numerical overhead associated to alternative methods like a random shift of the parameter.
Fabrice Rouillier
Polynomial system solving and computational geometry.
Abstract:
Many algorithms from computer algebra are used in computational geometry such as cylindrical algebraic decomposition for computing the topology of curves. They mostly concern univariate solving (resultants, Sturm sequences, Descartes method, etc.).
In this lecture, the goal is to show that recent algorithms for exact/certified multivariate solving can also be used efficiently in computational geometry after eventually formulating the problem in a different way.
Julian M. Smith
Aiming for a robust Boolean algorithm using approximate arithmetic
Abstract:
Robust implementations of the Boolean operation on boundary
representations of shapes are highly problematic when the
computations are based on inexact machine arithmetic. The
arithmetic computations required can yield inconsistencies in the
results, hindering the possibility of creating a topologically
correct boundary. These difficulties are compounded by the fact
that most operations perturb the boundary, which can lead to
geometric errors such as boundary self-intersections. While the
exact arithmetic paradigm can be used to avoid such problems, it
introduces new difficulties, such as performance degradation for
serial operations.
I present a topologically robust Boolean algorithm for
polygonal/polyhedral shapes. It is based on a hierarchy of
interdependent operations guaranteed to yield consistent
intermediate results; hence, the algorithm provably always generates
a topologically correct final result from topologically correct
input, irrespective of the extent of any numerical rounding. The
algorithm is tolerant to geometric errors, but does not resolve
them. For the result to be acceptable to end-users, it is generally
desirable to apply a smoothing post-process to remove marginal gaps,
slivers and overlaps. I go on to discuss my present work,
concerning how to devise a robust algorithm for resolving geometric
errors in a (topologically correct) shape representation. I discuss
both algorithms in the context of the requirements for a robust
approximate algorithm.
Elias P. Tsigaridas
Algebraic computations for non-linear computational geometry
Abstract:
We present new algorithmic and complexity results for the problems of real solving bivariate polynomial systems, computing the topology of a real plane algebraic curve and for the basic operations with two real
algebraic numbers. Our main ingredients are signed polynomial remainder
sequences, extended to many variables using the technique of binary
segmentation and the recent advances in the algorithms for real
root isolation of univariate integer polynomials.
George Tzoumas
Real-time implementation of the predicates for the Voronoi diagram of
ellipses.
Abstract:
The talk concentrates on the predicates for the Voronoi diagram of ellipses
from a certified numerics point of view. We apply interval arithmetic to the
required predicates and show that for InCircle, a certified numeric algorithm
that achieves quadratic convergence is able to answer the predicate in
real-time. The subdivision method for InCircle readily generalizes to smooth
convex curves. We develop interval-arithmetic techniques in C++ based on the
package ALIAS. For degenerate cases, we switch to an algebraic approach
applying real solving and resultant theory.
Julien Wintz
A subdivision arrangement algorithm for semi-algebraic curves.
Abstract:
We present a new method for computing the arrangement of semi-algebraic curves, based on subdivision methods. A subdivision approach is used to compute the topology of the algebraic objects and to segment the boundary of regions defined by these objects. An efficient insertion technique is described, which detects regions in conflict and updates the underlying arrangement structure.
We will describe the generic framework of this method, the main region insertion operation and the specializations of the key ingredients for the different types of objects: piecewise linear curves, parametric curves (polynomial rational, bspline or nurbs) and implicit curves. Each specialization of this generic arrangement algorithm will be illustrated using the algebraic-geometric modeler Axel.
Chee Yap
Complete Adaptive Algorithms for Curves and their Analysis.
Abstract:
Geometric operations on curves and surfaces can be based on algebraic techniques (e.g., cylindrical algebraic decomposition, resultants) or on numerical/geometric techniques (e.g., subdivision methods, marching cubes).
The latter techniques are practical, adaptive but usually incomplete.
We shall describe some new research to provide adaptive algorithms for geometric operations that are complete.
In particular, we address the problems of computing intersection of curves and topologically correct meshing of singular curves.
Another major challenge is the complexity analysis of such problems. We describe some progress in this direction.
last modified :
27-Sep-2007 2:10 PM
