Publications of Ioannis Z. Emiris

Publications (incomplete, reverse chronological order)

Books, Theses, and selected talks

Nonlinear Computational Geometry.
Eds I.Z. Emiris, F. Sottile, and T. Theobald. Series: The IMA Volumes in Mathematics and its Applications, vol. 151, 2010. Springer-Verlag.

Computational geometry: a modern algorithmic approach (in Greek), I.Z. Emiris, Klidarithmos, Athens 2008
Υπολογιστική Γεωμετρία: Μία σύγχρονη αλγοριθμική προσέγγιση, εκδόσεις Κλειδάριθμος, Αθήνα, 2008.
With a Chapter by Christodoulos Fragoudakis, and a Foreward by Leonidas Guibas.

Solving polynomial equations: Foundations, algorithms, and applications.
A. Dickenstein and I.Z. Emiris, eds., vol. 14 in: Algorithms and Computation in Mathematics, 2005, Springer-Verlag.
Preface

Compact formulae in Sparse elimination: Invited talk at ISSAC 2016, Waterloo (pdf).
Algorithmes algébriques et géométriques. Thèse d'habilitation à diriger des recherches, Jan. 2000, Univ. de Nice (ps.gz).
Sparse Elimination and Applications in Kinematics. Ph.D. Thesis, Dec.'94, UC Berkeley, (ps.gz).
Notes creuses sur l'élimination creuse (pdf).
Matrix Methods for Solving Algebraic Systems, Dagstuhl seminar (ps.gz).

Algebraic Algorithms

On the Bit Complexity of Solving Bilinear Polynomial Systems, with A. Mantzaflaris and E. Tsigaridas. ISSAC 2016 (tech. report)

Root counts of semi-mixed systems, and an application to counting Nash equilibria, with R. Vidunas. ISSAC-2014 (ACM DL).

Combinatorics of 4-dimensional Resultant Polytopes, with A.Dickenstein, V.Fisikopoulos. ISSAC'13

Single-lifting Macaulay-type formulae of generalized unmixed sparse resultants, with C. Konaxis, JSC 2011 (IHES Preprint 2010)

Multihomogeneous resultant formulae for systems with scaled support, with A. Mantzaflaris, (ISSAC 2009).

Multihomogeneous resultant formulae by means of complexes. JSC 2003. Preliminary: Multihomogeneous resultant matrices, with A. Dickenstein ISSAC'02 (Best paper award).

Hybrid sparse resultant matrices for bivariate systems, with D'Andrea (JSC'02).

An inversion-based implicitization method, with R. Sendra, 2002 (Tech.Report).

Computing sparse projection operators, with D'Andrea (Contemp.Math'01). Geometric viewpoint: Sparse Resultant Perturbations (ps.gz).

Matrices in elimination theory, with B. Mourrain, JSC'99 (ps.gz, pdf).

MARS: A Maple/Matlab/C Resultant-Based Solver, with Wallack and Manocha. (ISSAC'98).

On the Complexity of Sparse Elimination (J.Complexity). Prelim. Tech. Report.

Monomial Bases and Solution of Polynomial Systems, with A. Rege (ACM ISSAC)

Efficient Incremental Algorithms for the Sparse Resultant and the Mixed Volume, with J. Canny, JSC'95 (ps.gz, pdf). Prelim. conference version: Practical Method for the Sparse Resultant, with J. Canny, ACM ISSAC'93 (ps.gz, pdf).

A Subdivision-Based Algorithm for the Sparse Resultant, with J.F. Canny, Journal of ACM 2000 (jacm, ps.gz, pdf). Initial AAECC conference version: An Efficient Algorithm for the Sparse Mixed Resultant, with J. Canny (ps.gz, pdf).

Improved computation of determinants and resultants, with V. Pan: J. Complexity, 2005 (ps.gz). Short version in Proc. CASC (ps.gz).
Symbolic and numeric methods for exploiting structure in constructing resultant matrices, with V. Pan, JSC (ps.gz, pdf). Short version: The structure of sparse resultant matrices, with V. Pan, ISSAC'97 (ps.gz, pdf).
Certified Approximate Univariate GCDs, with A. Galligo and H. Lombardi (J.PureAppl.Algebra). First version: Numerical Univariate Polynomial GCD (The Mathematics of Numerical Analysis, Lect. Appl. Math., AMS)
Sign Methods for Counting and Computing Real Roots of Algebraic Systems, with B. Mourrain and M.N. Vrahatis (Tech.report).

Algebraic numbers and Arithmetic

Random polynomials and expected complexity of bisection methods for real solving, with A. Galligo and E.P. Tsigaridas. ISSAC 2010 (arxiv).

The DMM bound: multivariate (aggregate) separation bounds, with B. Mourrain and E.P. Tsigaridas. ISSAC 2010, Best paper award. (arxiv).

On the asymptotic and practical complexity of solving bivariate systems over the reals, with D. Diochnos and E. Tsigaridas. JSC 2009, special Issue. Preliminary: On the complexity of real solving bivariate systems, with D. Diochnos and E. Tsigaridas. ISSAC 2007. (pdf).

On the complexity of real root isolation using continued fractions, with E. Tsigaridas (TCS 2008), (preliminary ESA'06).

Real Algebraic Numbers: Complexity Analysis and Experimentations, with B. Mourrain and E. Tsigaridas (pdf) (pdf). In "Reliable Implementation of Real Number Algorithms: Theory and Practice", LNCS, 2006. Related: Computations with one and two real algebraic numbers, with E.P. Tsigaridas (arxiv).

Real algebraic numbers and polynomial systems of small degree, with E. Tsigaridas (TCS 2008). Real Solving of Bivariate Polynomial Systems, with E. Tsigaridas, CASC'05, LNCS (pdf). Computing with real algebraic numbers of small degree, with E. Tsigaridas, ESA'04 (pdf, ps.gz).

Root comparison techniques applied to the planar additively weighted Voronoi Diagram, with Karavelas (Siam/Acm SODA'03).

Algebraic methods for geometric predicates (talks in: Giens, France, 9/03, Athens, 11/03).

Sign determination in Residue Number Systems with H. Bronnimann, V. Pan and S. Pion. (TheorCS). Conf. version: Computing Exact Geometric Predicates Using Modular Arithmetic with Single Precision (ACM SCoG).

Modular Arithmetic for Linear Algebra Computations in the Real Field, with V.Y. Pan and Y. Yu, JSC (ps.gz, pdf).

Towards an Efficient Implementation of Interval Arithmetic, with R. Fateman. TR 693, UC Berkeley'92 (html).

Computational Geometry

Low-quality dimension reduction and high-dimensional approximate nearest neighbor, with E. Anagnostopoulos, I. Psarros. SoCG 2015.

Efficient edge-skeleton computation for polytopes defined by oracles, with V. Fisikopoulos and B. Gaertner. J. Symbolic Computation, 2015.

Efficient random-walk methods for approximating polytope volume, with V.Fisikopoulos. SoCG'14 (arxiv).

Nearest Neighbor Search in Lower Dimensional Flats, with I. Psarros: EuroCG 2014. Also with I. Psarros and K. Chanseau St-Germain: CGL TR.

Randomized kd-trees for Approximate Nearest Neighbor Search, with D. Nicolopoulos: CGL TR.

An output-sensitive algorithm for computing projections of resultant polytopes. With V. Fisikopoulos, C. Konaxis, and L. Penaranda. (Proc. ACM SoCG 2012) IJCGA.

Minkowski decomposition of convex lattice polygons, with E. Tsigaridas. In "Algebraic geometry and geometric modeling", Springer 2005 (pdf).

The predicates of the Apollonius diagram: algorithmic analysis and implementation, with M. Karavelas (CGTA) (Elsevier.web).

Towards an open curved kernel, with Kakargias, Pion, Teillaud, Tsigaridas: ACM SoCG'04 (ps.gz, pdf).

Computing integer points in Minkowski sums (ACM SoCG'00), (CGTA). Successive Linear Programs for Computing All Integral Points in a Minkowski Sum, with K. Zervoudakis. PCI'05 (pdf)

A Comparative Application of Convex Hull Algorithms in 2 and 3 Dimensions, with K. Zervoudakis (EuroCG'01).

How to count efficiently all affine roots of a polynomial system, with J. Verschelde (Disc.Appl.Math'99) (web).

Distributed computation of mixed volume (euroCG'97) with T. Giordano. Calcul distribué du volume mixte (rapport.ps.gz) with Giordano.

A Complete Implementation for Computing General Dimension Convex Hulls (IJCGA.dvi.gz)(ps.gz, 210KB).

Efficient Perturbations for Handling Geometric Degeneracies, with J.F. Canny and R. Seidel, Algorithmica (ps.gz, pdf). ACM SCoG Conf. version with J. Canny (ps.gz, pdf).

A General Approach to Removing Degeneracies, with J.F. Canny (SIAM J. of Computing) (prelim.version FOCS'91)

Geometric Modeling

Sparse implicitization by interpolation: Characterizing non-exactness, and an application to computing discriminants, with T. Kalinka, C. Konaxis, T. Luu Ba. J. CAD, Special Issue on Solid & Physical Modeling, 2013.

Implicitization of curves and (hyper)surfaces using predicted support. With T. Kalinka, C. Konaxis, and T. Luu Ba. Theor. Comp. Science, Special Issue on Symbolic-Numerical Algorithms, 2013.

Computing the Newton polytope of implicit curves, with C. Konaxis and L. Palios, "Math for Comp. Science" (Birkhauser), 2010. Also MEGA conf. 2007 (pdf). Talks at IMA and Oberwolfach (2007).

Implicitization exploiting Sparseness, with I.Kotsireas: Dimacs'04 (pdf). Implicit Polynomial Support Optimized for Sparseness, with Kotsireas: CGGM'03 (ps.gz, Springer.pdf).

Yet another algorithm for generalized Voronoi diagrams. With A. Mantzaflaris, and B. Mourrain. J. CAD, Special Issue on Solid & Physical Modeling, 2013.

Exact Delaunay graph of smooth convex pseudo-circles: general predicates, and implementation for ellipses, with E.P. Tsigaridas and G.M. Tzoumas: Symposium on Solid and Physical Modeling 2009 (pdf). Final version CAGD 2013.

Exact and efficient evaluation of the InCircle predicate for parametric ellipses and smooth convex objects, with G. Tzoumas. Computer-Aided Design 2008 . Preliminary: A Real-time and Exact Implementation of the Predicates for the Voronoi Diagram of Parametric Ellipses, with G. Tzoumas. In Proc. ACM Symp. Solid Physical Modeling (Beijing, 2007).

The Predicates for the Exact Voronoi Diagram of Ellipses under the Euclidiean Metric, with E. Tsigaridas, G. Tzoumas, Int. J. Comput. Geometry Appl., Special Issue, 2008 (pdf). Preliminary: The predicates for the Voronoi diagram of ellipses, with E. Tsigaridas, G. Tzoumas. (Proc. ACM Symp. Comput. Geom. 2006), (PDF).

Robotics

The assembly modes of rigid 11-bar linkages, with Guillaume Moroz. IFToMM 2011 (pdf).

Mixed Volume and Distance Geometry Techniques for Counting Euclidean Embeddings of Rigid Graphs, with E.P. Tsigaridas and A.E. Varvitsiotis (Book chapter, or prelim.version); Algebraic Methods for Counting Euclidean Embeddings of Rigid Graphs (Graph Drawing'09).

Design of a simple and modular 2-DOF ankle physiotherapy device relying on a hybrid serial-parallel robotic architecture, with C. Syrseloudis, T. Lilas, A. Maglara. J. Appl. Bionics & Biomechenics, Special issue on Assistive and Rehabilitation Robotics, 2011. A Parallel Robot for Ankle Rehabilitation-Evaluation and its Design Specifications, with C. Syrseloudis, IEEE BioInformatics & BioEngineering, Greece'08. Design Framework for a Simple Robotic Ankle Evaluation and Rehabilitation Device, with C. Syrseloudis, K. Maganaris and T. Lilas, IEEE Engineering Medicine & Biology'08.

Distributed routing in tree networks with few landmarks, with E. Markou and A. Pagourtzis, In: Proc. Workshop Combinat. & Algorithmic Aspects of Networking (CAAN), 2006, LNCS (pdf).

Calibration of Parallel Robots: on the Elimination of pose-dependent parameters, with D. Daney, Y. Papegay, E. Tsigaridas, J-P. Merlet. 2006, Proc. Europ. Conf. on Mechanism Science. PDF

Algebraic Elimination for Parallel Robot Calibration, with D.Daney (Iftomm'04). Robust parallel robot calibration with partial information, with Daney (ICRA'01). Variable elimination for reliable parallel robot calibration, with Daney (Comput. Kinematics'01).

A General Solver Based on Sparse Resultants: Numerical Issues and Kinematic Applications (html).

Force Closure Grasps of High Quality (postscript).

Structural Bioinformatics

A Workflow for Protein Homology Inference using Sequential and Structural Comparison, with A. Sharma and E.S. Manolakos, Hellenic Proteomics Society'09.

Algebraic methods for Protein structure prediction from RDC data, with S. Pantos. In: Intern. Workshop on Algebraic Biology 2007, Austria, LNCS 4545.

Beta-barrel Transmembrane Proteins: Geometric Modelling, Detection of Transmembrane Region, and Structural Properties, with I. Valavanis and P. Bagos. Computational Biology and Chemistry, 2006. (article)

Algebraic algorithms for determining structure in biological chemistry, with E. Fritzilas and D. Manocha: Intern. J. Quantum Chemistry, Spec. Issue on Symbolic Methods, 2005 (pdf).

Molecular Conformation Search by Distance Matrix Perturbations, with T.G. Nikitopoulos: J.Math.Chem 2005 (ps.gz, pdf) (web).

Computer Algebra methods for studying and computing molecular conformations, with B. Mourrain (Algorithmica).

Ioannis Z Emiris, ErGA Lab