EMIRIS , Ioannis Z.

Approximate Nearest Neighbor (ANN) search is a fundamental computational problem that has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets, whereas complex shapes have not been sufficiently addressed. Here, we focus on distance functions between discretized curves in Euclidean...

We present state-of-the-art computational methods which are instrumental in autonomous maritime operations, and optimization of routing, scheduling as well as loading. Our aim is to survey mature algorithmic approaches developed within the Lab of Geometric & Algebraic Algorithms, towards exploiting intelligence and automation in modern shipping...

Randomized dimensionality reduction has been recognized as one of the fundamental techniques in handling high-dimensional data. Starting with the celebrated Johnson-Lindenstrauss Lemma, such reductions have been studied in depth for the Euclidean (L2) metric, but much less for the Manhattan (L1) metric. Our primary motivation is the approximate...

The approximate nearest neighbor problem (e-ANN) in high dimensional Euclidean space has been mainly addressed by Locality Sensitive Hashing (LSH), which has polynomial dependence in the dimension, sublinear query time, but subquadratic space requirement. In this paper, we introduce a new definition of "low-quality" embeddings for metric...

The construction of r-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate r-nets with respect to Euclidean distance. For any fixed ϵ>0, the approximation factor is 1+ϵ and the complexity is polynomial in the dimension...

The construction of r-nets offers a powerful tool in computational and metric geometry. We focus on high-dimensional spaces and present a new randomized algorithm which efficiently computes approximate $r$-nets with respect to Euclidean distance. For any fixed \epsilon>0, the approximation factor is 1+\epsilon and the complexity is polynomial...

Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal...

A new algorithm for calibrating Gough platforms is proposed. It requires internal sensor measurements and only the position information provided by external sensors. It removes the need to measure orientation, which is intricate and error-prone, by algebraic elimination. This approach, relying on resultants and dialytic elimination, produces an...

We study overconstrained polynomial systems from an algebraic and numerical perspective in order to improve the accuracy and reliability of Gough platform calibration. By elimination theory, we may limit ourselves to measuring only the position information by external sensors, besides internal sensor measurements. Measuring orientation, which...

The Canny-Emiris formula gives the sparse resultant as a ratio between the determinant of a Sylvester-type matrix and a minor of it, by a subdivision algorithm. The most complete proof of the formula was given by D'Andrea et al. in [9] under general conditions on the underlying mixed subdivision. Before the proof, Canny and Pedersen had...

We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear inequalities. We implement and evaluate practical randomized algorithms for accurately approximating the polytope's volume in high dimensions (e.g. one hundred). To carry out this efficiently we experimentally...

We address a central question in rigidity theory, namely to bound the number of Euclidean or spherical embeddings of minimally rigid graphs. Since these embeddings correspond to the real roots of certain algebraic systems, the same enumerative question can be asked in complex spaces. Bézout's bound on the quadratic equations that capture the...

We tackle the problem of efficiently approximating the volume of convex polytopes, when these are given in three different representations: H-polytopes, which have been studied extensively, V-polytopes, and zonotopes (Z-polytopes). We design a novel practical Multiphase Monte Carlo algorithm that leverages random walks based on billiard...

We offer a closed form bound on the m-Bézout bound for multi-homogeneous systems whose equations include two variable subsets of the same degree. Our bound is expectedly not tight, since computation of the m-Bézout number is P-hard by reduction to the permanent. On the upside, our bound is tighter than the existing closed-form bound derived...

In this paper we derive aggregate separation bounds, named after Davenport-Mahler-Mignotte (\dmm), on the isolated roots of polynomial systems, specifically on the minimum distance between any two such roots. The bounds exploit the structure of the system and the height of the sparse (or toric) resultant by means of mixed volume, as well as...

International audience

The aim of this paper is to study the distribution of portfolio returns across portfolios, and for given asset returns. We focus on the most common type of investment, considering portfolios whose weights are non-negative and sum up to 1. We provide algorithms and formulas from computational geometry and the literature on splines to compute the...

We design and implement an efficient and certified algorithm for the computation of Voronoi Diagrams (VD's) constrained to a given domain. Our framework is general and applicable to any VD-type where the distance field is given explicitly or implicitly by a polynomial, notably the anisotropic VD or VD's of non-punctual sites. We use the...

Our probabilistic analysis sheds light to the following questions: Why do random polynomials seem to have few, and well separated real roots, on the average? Why do exact algorithms for real root isolation may perform comparatively well or even better than numerical ones? We exploit results by Kac, and by Edelman and Kostlan in order to...

Today, there is a growing number of digital assets, often built on questionable technical foundations. We design and implement supervized learning models in order to explore different aspects of a cryptocurrency affecting its performance, its stability as well as its daily price fluctuation. One characteristic feature of our approach is that we...

We present algorithmic, complexity and implementation results concerning real root isolation of a polynomial of degree $d$, with integer coefficients of bit size $\le\tau$, using Sturm (-Habicht) sequences and the Bernstein subdivision solver. In particular, we unify and simplify the analysis of both methods and we give an asymptotic complexity...

We examine volume computation of general-dimensional polytopes and more general convex bodies, defined by the intersection of a simplex by a family of parallel hyperplanes, and another family of parallel hyperplanes or a family of concentric ellipsoids. Such convex bodies appear in modeling and predicting financial crises. The impact of crises...

International audience

We exploit a recent computational framework to model and detect financial crises in stock markets, as well as shock events in cryptocurrency markets, which are characterized by a sudden or severe drop in prices. Our method manages to detect all past crises in the French industrial stock market starting with the crash of 1929, including...

Large scale duplicate detection, clustering and mining of documents or images has been conventionally treated with seed detection via hashing, followed by seed growing heuristics using fast search. Principled clustering methods , especially kernelized and spectral ones, have higher complexity and are difficult to scale above millions. Under the...