Homepage

Arno Eigenwillig

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E14, room 329 [local street map]
66123 Saarbrücken
Germany

E-Mail: arno@mpi-sb.mpg.de
Phone number: +49-681-9325-129 (on campus: 92-129)
Fax number: +49-681-9325-199
Erdös number: (3, Mehlhorn(2, Aronov(1), Kratsch(1)), Yap(2, Pach(1), Pollack(1))) [data].

My last name follows standard German pronunciation and sounds similar to eigenvalue.

Work

I am a PhD student in Department 1: Algorithms and Complexity (head: Kurt Mehlhorn) of the Max-Planck-Institut für Informatik (MPII). I am working in the field of exact non-linear computational geometry. Parts of my work belong to the EXACUS project at MPII. EXACUS is related to the European Union's ECG and ACS projects.

Research Interests

Exact non-linear computational geometry.
Univariate real root isolation.

Publications

You can find my publications in the list below or in the MPII publications and MPII research reports databases.

The copyright for my publications is reserved. Where a pre-print or author-prepared version of a paper is provided, this is done with permission of the publisher as a means of timely communication among scholars, without permission for further distribution. The definitive version of a paper is the published version.

Scientific Papers:

A. Eigenwillig, M. Kerber:
Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves. [PS] [PDF]
19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp.122-131.
© SIAM, 2008. Posted here is an author-prepared version of this article. Not for redistribution. The definitive version was published in the Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008).
A. Eigenwillig, M. Kerber, N. Wolpert:
Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. [PS] [PDF]
2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp.151-158.
© ACM, 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007).
A. Eigenwillig, L. Kettner, N. Wolpert:
Snap Rounding of Bézier Curves. [PS] [PDF]
23rd Annual Symposium on Computational Geometry (SCG 2007), pp.158-167.
© ACM, 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 23rd Annual Symposium on Computational Geometry (SCG 2007).
Here is an addendum [PS] [PDF] to the published paper.
A. Eigenwillig, V. Sharma, C. Yap:
Almost Tight Recursion Tree Bounds for the Descartes Method. [PS] [PDF]
2006 International Symposium on Symbolic and Algebraic Computation (ISSAC 2006), pp.71-78.
V. Sharma and me received the Distinguished Student Author Award for this paper (shared with G. Moroz).
© ACM, 2006. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation (ISSAC 2006).
A. Eigenwillig:
On Multiple Roots in Descartes' Rule and Their Distance to Roots of Higher Derivatives [PS] [PDF]
Journal of Computational and Applied Mathematics 200(1), pp. 226-230, 2007.
© 2006.
A. Eigenwillig, L. Kettner, E. Schömer, N. Wolpert:
Exact, Efficient, and Complete Arrangement Computation for Cubic Curves. [PS] [PDF]
Computational Geometry: Theory and Applications 35(1-2), pp.36-73, 2006.
© Elsevier B.V., 2005.
E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Schömer, N. Wolpert:
EXACUS: Efficient and Exact Algorithms for Curves and Surfaces. [PS] [PDF]
13th European Symposium on Algorithms (ESA 2005), Springer LNCS 3669, pp. 155-166.
© Springer-Verlag, 2005.
A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, N. Wolpert:
A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. [PS] [PDF]
8th Internat. Workshop on Comp. Algebra in Sci. Computing (CASC 2005), Springer LNCS 3718, pp. 138-149.
© Springer-Verlag, 2005.
In addition to this proceedings article, there is a web page with benchmarks for the proposed algorithms.
A. Eigenwillig, L. Kettner, E. Schömer, N. Wolpert:
Complete, Exact, and Efficient Computations with Cubic Curves. [PS] [PDF]
20th Annual Symposium on Computational Geometry (SCG 2004), pp.409-418.
© ACM, 2004. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 20th Annual Symposium on Computational Geometry (SCG 2004).
A. Eigenwillig, E. Schömer, N. Wolpert:
Sweeping Arrangements of Cubic Segments Exactly and Efficiently. [PS] [PDF]
Technical Report ECG-TR-182202-01, 2002.
© 2002.
E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, K. Mehlhorn, E. Schömer:
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons.
10th European Symposium on Algorithms (ESA 2002), Springer LNCS 2461, pp. 174-186.
© 2002.

General audience:

A. Eigenwillig, K. Mehlhorn:
Multiplikation langer Zahlen (schneller als in der Schule) [HTML] [PDF].
Der 16. Algorithmus der Woche im Informatikjahr 2006.
© 2006.

Talks (selected):

Oberseminar Computational Mathematics at University of Kassel, Germany:
Klassische Verfahren zur Isolierung reeller Polynomnullstellen.
ISSAC 2006: Almost Tight Recursion Tree Bounds for the Descartes Method [slides]
(joint work with Vikram Sharma and Chee Yap, see also proceedings article above).
MPII-D1 Mini Course on Algebra and Geometry
Sweeping Arrangements of Cubic Segments Exactly and Efficiently
DIMACS Workshop on Implementation of Geometric Algorithms (Dec 2002, in place of N. Wolpert)
ECG Workshop on Arrangements of Curves and Surfaces (Dec 2002)
Lorraine-Saarland Workshop on Geometry and CAD (April 2003).

Theses:

A. Eigenwillig:
Exact Arrangement Computation for Cubic Curves [PS] [PDF]
Master's thesis (Diplomarbeit), 138 pages, Saarland University, 30th July 2003.

Education

2004-present:
PhD student of computer science at Max-Planck-Institut für Informatik (MPII) in Saarbrücken, Germany, partially supported by a scholarship from the DFG-Graduiertenkolleg »Leistungsgarantien für Rechnersysteme« (Research Training Group on »Quality Guarantees for Computer Systems«).
July 2003:
Master's degree (Diplom) in computer science with a thesis on »Exact Arrangement Computation for Cubic Curves«.
The thesis was decorated by FdSI e.V. with a Günter Hotz Award for outstanding cs graduates.
2000-2003:
Student of computer science (major) and mathematics (minor) at Universität des Saarlandes at Saarbrücken, Germany, supported by a scholarship from the Studienstiftung des deutschen Volkes (German National Academic Foundation).
1999-2000:
Student of computer science at the University of Edinburgh, Scotland, supported by a scholarship from the DAAD (German Academic Exchange Service).
September 1999:
Intermediate exam (Vordiplom) in mathematics
Intermediate exam (Vordiplom) in computer science
1997-1999:
Undergraduate student of computer science and mathematics (double-major) at Rheinische Friedrich-Wilhelms-Universität Bonn, Germany.