Colloquia Patavina: How many points can be reconstructed from k projections?


Martedi' 15 Aprile 2008 alle ore 16:00 in aula 1A/150 della Torre Archimede il Professor Jiri Matousek della Charles University di Praga terra' una conferenza della serie Colloquia Patavina dal titolo "How many points can be reconstructed from k projections?"

La Commissione Colloquia
M. A. Garuti, M. Pavon, M. Pitteri, F. Rossi

How many points can be reconstructed from k projections?

Jiri Matousek (Charles Univ., Prague)

Martedi' 15 Aprile 2008, ore 16:00
Aula: 1A/150, Torre Archimede

Let A be an n-point set in the plane. A discrete X-ray of A in direction u gives the number of points of A on each line parallel to u. We define F(k) as the maximum number n such that there exist k directions u_1,...,u_k such that every set of at most n points in the plane can be uniquely reconstructed from its discrete X-rays in these directions. We establish an almost exponential lower bound F(k)>2^(ck/log k), by a combination of linear-algebraic, graph-theoretic, and probabilistic arguments, and an upper bound F(k) < C^k for a constant C approximately 1.8.

-Breve curriculum
- Born 10 March 1963 in Prague
- Discrete mathematics and theoretical informatics
- Member of LS since 2006

-Education and Professional Preparation
- Undergraduate studies, Faculty of Mathematics and Physics at Charles University in Prague, 1981-1986
- Internal postgraduate studies, Faculty of Mathematics and Physics, Charles University, 1987
- External postgraduate studies, Faculty of Mathematics and Physics, Charles University, 1987-1991

- Faculty of Mathematics and Physics, Charles University (University lecturer 1987-1995, Assistant Professor 1995-2000, full Professor 2000- )
- 1991 (January-June), Georgia Institute of Technology, Atlanta, Ga, visiting Professor
1992, Humboldt Fellowship, Freie University in Berlin

-Significant Awards
1986 - Award of the Czechoslovak Academy of Sciences
1996 - Award of the 2nd European Congress of Mathematics for Young Mathematicians

-Selection of Publications
- J. Matousek, M. Sharir, E. Welzl: A subexponential bound for linear programming, Algorithmica 16(1996) 498-516.
- J. Matousek: Improved upper bounds for approximation by zonotopes, Acta Mathematica 177(1996) 55-73.
- J. Matousek: Lectures on Discrete Geometry, Graduate Texts in Mathematics, Volume 212, 481pp, Springer, New York, 2002.
- J. Matousek: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry, Universitext, Springer, Berlin etc., 196pp, 2003.
- J. Matousek: Geometric Discrepancy. An Illustrated Guide, 288 pp, Springer-Verlag, Berlin etc., 1999.
- J. Matousek: Construction of epsilon-nets, Discr. Comput. Geom. 5(1990) 427-448.
- J. Matousek, J. Spencer: Discrepancy in arithmetic progressions, J. Amer. Math. Soc. 9,1(1996) 195-204.
- J. Matousek: On the chromatic number of Kneser hypergraphs, Proc. Amer. Math. Soc. 130(2002), 2509-2514.
- I. Bárány, J. Matousek: A Fractional Helly theorem for convex lattice sets, Adv. Math. 174(2003) 227-235.
- M. Kiwi, M.Loebl, J. Matousek: Expected length of the longest common subsequence for large alphabets, Adv. Math. 197(2005) 480-498.

Download Colloquia Patavina

Download Web Site