Algebraic Algorithms

Polynomial system solving, sparse/toric elimination theory, structured matrices. Resultants reduce system solving to linear algebra.
Newton polytopes provide the bridge between algebra and combinatorial geometry.
Optimal sparse resultant matrices for
multihomogeneous polynomial systems
(article), and
MAPLE software MHRES.
Macaulaytype formulae for sparse resultants of generalized unmixed systems
(article).
More Algebraic software.

Real solving, Real algebraic numbers.
Solvers based on Continued Fractions and Sturm sequences.
Software tools in C++
(Mathemagix):
module Realroot, intervalNewton method,
solvers for polynomial systems (subdivision methods).
MAPLE software SLV for real algebraic numbers,
real solving of equations and bivariate systems.
Benchmarking of blackbox univariate real solvers.
Geometric Algorithms

Geometric Modeling and Nonlinear Computational geometry.
Exact and approximate implicitization of parametric hypersurfaces by
interpolation using matrix operations, and sparse elimination for exploiting
structure
(article).
Extensions to space curves and objects defined by point clouds
(Wiki page).
Voronoi diagrams of circles and ellipses
(IMA nugget),
alphashapes for robust modeling of 3D objects,
arrangements of curved objects (talk)
on CGAL.
Python projects and CGALPython bindings, including visibility tools:
webpage.

Convex geometry in general dimension.
Random walks for approximating polytope volume (software).
Convex hull and symbolic perturbation, mixed volume
(software).
Regular fine mixed subdivisions of Minkowski sums,
regular triangulations, secondary polytopes, resultant polytopes
(software).
Minkowski decomposition (webpage):
optimal algorithms with a fixedsize summand, approximation of general (NPhard) problem.
Polytopal computations:
normals, faces, ridges, extreme or interior points
(module Polytopix in Mathemagix).

Geometric search in high dimensions.
kdGeRaf: Generalized Randomized kdtrees for fast approximate
nearestneighbors of points, in very high dimensions
(competitive in dimension of up to 10,000):
Web tool,
Software,
further info.
Dimensionality reduction by a weak version of the JL lemma,
and nearlyrecord complexity for ANN
(SoCG 2015).
Fast, highdimensional, approximate $r$nets
(SODA 2017).

Clustering algorithms.
IQmeans: Clustering for big data: we improve kmeans
by reverse assignment, combined with ideas from product quantization
(image), to cluster 100 Mil SIFT images in 1hr
(Software tool IQmeans,
paper at ICCV 2015).
Structural bioinformatics
and Robotics

Structure of Transmembrane proteins.
Geometric modelling of βbarrels and detection of the transmembrane region of a βbarrel transmembrane protein.
Given a PDB file, the transmembrane region is detected by profiling the external residues of the βbarrel along its axis in terms of hydrophobicity and existence of aromatic and charged residues.
Our geometric modeling of the barrel relies on combining
nonlinear least square minimization and a genetic algorithm.
TbBTool is the software tool.
Paper.

Lakes
is a software tool
for the prediction of protein binding sites.
It analyzes the solvent and its contacts with proteins
and defines clusters of water molecules,
which mark potentially exposed interaction and binding sites
of the protein.
Contact: Dr Thanassis Tartas.
Figure: black is the protein, colored are the oxygen atoms of clusters, red being the largest cluster.

Molecular conformations in Structural bioinformatics.
Enumeration of all possible conformations of (small) molecules/proteins under geometric constrains; CSpace
(interactive example).
Determination of active sites by alphashapes, Sampling of rotamers,
and clustering to deduce structural determinants.
Paper by Emiris, Fritzilas, Manocha.
Graph embedding in Euclidean spaces, rigidity theory,
distance geometry to compute conformations from NMR data.

Robot kinematics.
Robust calibration of parallel robots (by applying elimination techniques),
forward kinematics of Stewart/Gough platforms,
and design of robotic platforms for medical applications such as physiotherapy.