Discrete and Computational Geometry

1989-1990

September 29, 1996

We are writing this report six years after the conclusion of the Special Year on Discrete and Computational Geometry at DIMACS. Rather than attempting the impossible task of mentioning all the accomplishments and difficulties of the year and their impact as we understand them now, we follow the tradition of these reports and provide only an incremental update to the various reports that have been made in the past, specifically in 1990 and 1992.

Among the most noteworthy of the accomplishments that have been mentioned in previous reports are the linear time triangulation algorithm of Chazelle, the solution of the Gilbert-Pollack conjecture by Du and Hwang, and the efficient deterministic algorithm of Matou\v{s}ek to find $1\over r$ cuttings. The role of these results is outlined in the 1990 annual report. The work of Matou\v{s}ek is deeply connected to the progress on randomized algorithms which was described in earlier reports. This work has continued and has been followed up by the efficient derandomization of many geometric algorithms. We now have optimal algorithms for convex hulls in all dimensions (Chazelle).

We also append a brief memoir by Carl Lee who spent his sabbatical year participating in the 1989-90 Special Year.

The three post-docs at the special year were Pankaj Agarwal, Boris Aronov, and Rephael Wenger. Agarwal is now an associate professor at Duke University, Aronov is an associate professor at Polytechnic University, and Wenger is an associate professor at Ohio State University. Agarwal reports that the atmosphere at DIMACS was supportive and nurturing. He had the opportunity to meet many of the leading researchers and started significant collaborations with Matou\v{s}ek, Overmars, and Welzl, all of which have continued for many years (see [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21] for a sample of his papers that were significantly influenced by his year at DIMACS). Aronov felt that DIMACS provided an exceptional opportunity to interact with leading researchers and the time and space to work productively (see [50, 51, 52, 53, 54, 55, 56, 57, 58, 59] for a sample of papers that were siginificantly influenced by his year at DIMACS). Wenger continued and still continues a fertile collaboration with Goodman and Pollack which has led to several papers on geometric transversal theory and several others on arrangements of pseudolines (see [22, 23, 24, 25, 26, 27, 28]). It seems clear that talented post-docs were chosen and that they profited from the environment during the special year.

Prabhu Nagashubana, a graduate student at NYU, spent most of the year visiting DIMACS. He collaborated with another graduate student, William Jockusch, who was visiting DIMACS, as well as with Carl Lee. Prabhu developed an extensive collaboration with Micha Perles who was visiting DIMACS for the whole year. This collaboration led to a series of results, some of which are still emerging (see ([48, 49]). Prabhu is now an associate professor at Purdue University.

The international flavor of the year stimulated cross-fertilization between communities that had not previously interacted. We mention a few notable examples among many others.

Nicolai Mn\"ev visited DIMACS for the workshop on Arrangements. His dramatic universality theorems (see [29, 30]) were just beginning to be known and digested in the west. Two immediate consequences of these results are that the realizability problem of oriented matroids is polynomially reducible to the existential theory of the reals and is hence NP-hard, and that the

M.-F. Roy attended the workshop on algebraic methods and began a fruitful collaboration between real algebraic geometry (Roy) and discrete and computational geometry (Pollack). During the past four years they have written several papers (most joint with Pollack's former Ph. D student S. Basu) improving the best algorithms for quantifier elimination over real closed fields, the existential theory of the reals, the construction of roadmaps for arbitrary semi-algebraic sets, finding bounds on the number of cells defined by a family of polynomials, as well as extending all of these results to the case where the problem lives on a subvariety of lower dimension (see [33, 34, 35, 36, 37, 38, 39, 40, 41]).

Earlier reports have mentioned the new directions initiated by Gelfand and Rybnikov.

Another new direction initiated at the special year which generated a great deal of new work, some of which is only coming out now, was stimulated by Micha Perles who spent all of the special year at DIMACS.

During the special year, Perles offered a course at Rutgers University devoted to ``geometric graphs." He raised several unsolved problems and made many exciting conjectures. Work on some of these conjectures was initiated during the Special Year (see [42, 43, 44]). This is now a very active area of research. The most recent developments are summarized in Chapter 14 of [45]. Significant progress has been made concerning Conway's Thrackle Conjecture [46], and it was proved that every quasi-planar graph has a linear number of edges [47]. The field now receives a lot of attention from theoreticians and practitioners of the graph drawing community as well.

The special year was the first of many special years at DIMACS and suffered the birth pains of any new enterprise. In particular, for the first half of the year there was an absence of adequate office space for visitors and a common space which would facilitate their interactions. Given this difficulty it is remarkable that so many productive interactions were facilitated. The computer facilities were also weak during the first half of the year. It would have been helpful to have assistance to encourage the implementation of algorithms which were developed during the special year. It would be a good idea to stimulate more interaction between the geometry community and more applied areas related to geometry such as slid modeling, graphics, geographical informations systems and computer vision.

[1] P.K. Agarwal, H. Edelsbrunner, and O. Schwarzkopf, Euclidean minimum spanning tree and bichromatic closest pairs, and E. Welzl,

[2] P.K. Agarwal and M. Sharir, Off-line dynamic maintenance of the width of a planar point set,

[3] P.K. Agarwal and B. Aronov, Counting facets and incidences,

[4] P.K. Agarwal, J. Matou\v{s}ek, and S. Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions,

[5] P.K. Agarwal, M. van Kreveld, and M. Overmars, Intersection queries in sets of discs,

[6] P.K. Agarwal and J. Matou\v{s}ek, Relative neighborhood graphs in three dimensions,

[7] P.K. Agarwal and M. Sharir, Applications of a new space partitioning technique,

[8] P.K. Agarwal and M. Sharir, Circle shooting in a simple polygon,

[9] P.K. Agarwal and M. Sharir, Circular visibility of a simple polygon >from a fixed point,

[10] P.K. Agarwal, B. Aronov, M. Sharir, and S. Suri, Selecting distances in the plane,

[11] P.K. Agarwal, M. Pellegrini, and M. Sharir, Counting circular arc intersections,

[12] P.K. Agarwal and J. Matou\v{s}ek, Ray shooting and parametric search,

[13] P.K. Agarwal, M. van Kreveld and M. Overmars, Intersection queries in curved objects,

[14] P.K. Agarwal, A. Efrat, M. Sharir, and S. Toledo, Computing a Segment-Center for a planar point set,

[15] P.K. Agarwal and M. Sharir, Planar geometric location problems,

[16] P.K. Agarwal and J. Matou\v{s}ek, Range searching P.K. Agarwal semialgebraic sets,

[17] P.K. Agarwal, N. Alon, B. Aronov, and S. Suri, Can visibility graphs be represented compactly?

[18] P.K. Agarwal and J. Matou\v{s}ek, Dynamic half-space searching and its applications,

[19] P.K. Agarwal, B. Aronov, J. O'Rourke, and C. Schevon, Star unfolding of a polytope P.K. Agarwal applications,

[20] P.K. Agarwal, J. Matou\v{s}ek and O. Schwarzkopf, Computing many faces in arrangements of lines and segments,

[21] P.K. Agarwal, M. de Berg, J. Matou\v{s}ek, and O. Schwarzkopf, Constructing levels in arrangements and higher order Voronoi diagrams,

[22] S. Cappell, J. E. Goodman, J. Pach, R. Pollack, M. Sharir, and R. Wenger, Common tangents and common transversals,

[23] J. E. Goodman, R. Pollack, and R. Wenger, Geometric Transversal Theory, in

[24] J. E. Goodman, R. Pollack, and R. Wenger, On the connected components of the space of line transversals to a family of convex sets,

[25] J. E. Goodman, R. Pollack, and R. Wenger, There are uncountably many universal topological planes,

[26] J. E. Goodman, R. Pollack, and R. Wenger, Bounding the number of geometric permutations induced by

[27] J. E. Goodman, R. Pollack, R. Wenger, and T. Zamfirescu, Every arrangement extends to a spread,

[28] J. E. Goodman, R. Pollack, R. Wenger, and T. Zamfirescu, Arrangements and topological planes,

[29] N.E. Mn\"ev, On manifolds of combinatorial types of projective configurations and convex polyhedra,

[30] N.E. Mn\"ev, The universality theorems of the classification problem of configuration varieties and convex polytope varieties in

[31] N. Mn\"ev, The universality theorem on the oriented matroid stratification of the space of real matrices, in

[32] P. Shor, Stretchability of pseudolines is NP-hard, in

[33] R. Pollack and M.-F. Roy, On the number of cells defined by a set of polynomials,

[34] S. Basu, R. Pollack and M.-F. Roy, Computing a set of points meeting every cell defined by a family of polynomials on a variety, in

[35] S. Basu, R. Pollack and M.-F. Roy, On the number of cells defined by a family of polynomials on a variety,

[36] S. Basu, R. Pollack and M.-F. Roy, On the combinatorial and algebraic complexity of Quantifier Elimination, in

[37] S. Basu, R. Pollack and M.-F. Roy, On the combinatorial and algebraic complexity of Quantifier Elimination (Extended Abstract),

[38] S. Basu, R. Pollack and M.-F. Roy, A new algorithm to find a point in every cell defined by a family of polynomials, in

[39] Computing Roadmaps of Semi-algebraic Sets (Extended Abstract),in

[40] S. Basu, R. Pollack and M.-F. Roy, Computing Roadmaps of Semi-algebraic Sets on a Variety (Extended Abstract) in

[41] S. Basu, R. Pollack and M.-F. Roy, On Computing a Set of Points meeting every Semi-algebraically Connected Component of a Family of Polynomials on a Variety,

[42] V. Capoyleas and J. Pach, A Tur\'an-type theorem on chords of a convex polygon,

[43] J. Pach and J. T\"or\H ocsik, Layout of rooted trees, in

[44] Y. Ikebe, M. Perles, A. Tamura, and S. Tokunaga, The rooted tree embedding problem into points in the plane,

[45] J. Pach and P.K. Agarwal, Combinatorial Geometry, J. Wiley, (1995).

[46] L. Lov\'asz, J. Pach, and M. Szegedy, On Conway's thrackle conjecture, in

[47] P. Agarwal, B. Aronov, J. Pach, R. Pollack, and M. Sharir, Quasi-planar graphs have a linear number of edges,

[48] Perles, M.A., and Prabhu, N., A Property of Graphs of Convex Polytopes,

[49] Perles, M.A. and Prabhu, N., Transversals of Polytopes,

[50] B. Aronov, B. Chazelle, H. Edelsbrunner, L.J. Guibas, M. Sharir, and R. Wenger, Points and triangles in the plane and halving planes in space,

[51] B. Aronov and P.K. Agarwal, Counting facets and incidences,

[52] B. Aronov, H.~Edelsbrunner, L. Guibas, and M. Sharir, The number of edges of many faces in a line segment arrangement,

[53] B. Aronov and J. O'Rourke, Nonoverlap of the star unfolding,

[54] B. Aronov, R. Seidel and D. Souvaine, Compatible triangulations,

[55] B. Aronov, P. Erd\H{o}s, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman, Crossing families, with P. Erd\H{o}s, W. Goddard, D.J. Kleitman, M. Klugerman, J. Pach, and L.J. Schulman,

[56] P. Agarwal, N. Alon, B. Aronov, and S. Suri, Can visibility graphs be represented compactly?

[57] B. Aronov and J. Matou\v{s}ek, On stabbing triangles by lines in 3-space,

[58] Star unfolding of a polytope with applications, B. Aronov, P.K. Agarwal, J. O'Rourke, and C.A. Schevon,

[59] J. Richter-Gebert and G. Ziegler, Realization spaces of 4-polytopes are Universal,

[60] H. Guenzel, The universal partition theorem for oriented matroids,

[61] H. Guenzel, On the universal partition theorem for 4-polytopes, preprint.

Brief retrospective on the impact of my stay at DIMACS

Carl Lee

I was invited to spend the 1989-90 academic year at DIMACS in conjunction with my first sabbatical. The experience was unquestionably extremely significant for my professional development.

- I had the time to bring some of my mathematical work to fruition, and the
quality of the results was enhanced by my discussions with the DIMACS
members. More than once I learned of specific ideas and results that
directly related to my work.
Three preprints were completed during this time:

- (a) C.W. Lee, Regular triangulations of convex polytopes,
*DIMACS Series in Discrete Mathematics and Theoretical Computer Science*, volume 4, 1991, 443--456.

- (b) C.W. Lee, Winding numbers and the generalized lower-bound
conjecture,
*DIMACS Series in Discrete Mathematics*, volume 6, 1992, 209--219.

- (c) G. Bohus, W. Jockusch, C.W. Lee and N. Prabhu, On a
triangulation of the 3-ball and the solid torus,
*Discrete Math.*, to appear.

- (a) C.W. Lee, Regular triangulations of convex polytopes,
- I had the opportunity to discuss mathematics with the visitors
in residence: postdoctoral
fellows (Pankaj Agarwal, Boris Aronov, and Raphael Wenger), and visiting
faculty (Micha Perles), as well as interact with the many other affiliated
faculty and students. I took advantage of all DIMACS had to offer:
informal discussions, the DIMACS seminars, the several week-long
workshops, the seminars nearby, especially the geometry seminars
at the Courant Institute, Perles' course, and attendance at relevant
conferences elsewhere during this period of time. My research and papers
directly benefitted from the environment in which individuals
in my area of study were brought together with those in
computational geometry, and in which well-established researchers interacted
with recent Ph.D.'s. The level of interaction increased dramatically
once we moved into a common building.

- During one of the workshops I gave a talk on triangulations
of polytopes, which provided the basis for the chapter on
Subdivisions and Triangulations of Polytopes for the
*CRC Handbook of Discrete and Computational Geometry*.

- Perhaps the greatest long-term effect of my stay at DIMACS was
my recent publications:

- (a) C.W. Lee, Generalized stress and rigidity, in
*Polytopes: Abstract, Convex and Computational,*T. Bisztriczky, P. McMullen, R. Schneider, and A. Ivi\'c Weiss, editors, Volume 440, NATO ASI Series C: Mathematical and Physical Sciences, Kluwer, 1993, 249--271.

- (b) C.W. Lee, P.L.-spheres, convex polytopes, and stress,
*Discrete and Computational Geometry***15**(1996) 389--421.

*g*-Theorem.

- (a) C.W. Lee, Generalized stress and rigidity, in
- Finally I spent some time on the development of some
presentations on polytopes for high school and college teachers, which
were given in summer workshops sponsored by COMAP.

DIMACS home page

Contacting the Center

Document last modified on May 1, 1998.