The Impact of the DIMACS Special Year on
Discrete and Computational Geometry
1989-1990

J.E. Goodman, J. O'Rourke, J. Pach and R. Pollack (chair)
September 29, 1996

1 Introduction

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.

2 Post-docs and students

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.

3 New international interactions

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.

3.1 Universality and NP-hardness

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 isotopy conjecture , stated 30 years earlier, is false in the most dramatic way. At the workshop, Peter Shor worked with Mn\"ev and helped edit Mn\"ev's paper [31] for the volume in the DIMACS series devoted to the special year. Out of this work, Shor found an independent proof of the NP-hardness of the stretchability of pseudolines (see [32]). This workshop, as well as the publications that came out of it, made these theorems accessible to the community. During the following years much exciting work in this area has emerged: H. G\"unzel gave an independent proof of the universality theorem [60], and J. Richter-Gebert proved a universality theorem for 4-polytopes [59] and for 6-polytopes. His proof relies significantly on what he calls the "Shor encoding," which Shor developed in [32]. G\"unzel also has an independent proof of the universality theorem for 4-polytopes [61]. This theorem, apart from its own significance, immediately yields proofs of many previous results which had distinguished 3-polytopes from polytopes in higher dimensions.

3.2 Real algebraic vs. computational geometry

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]).

4 New directions

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.

5 Criticisms and suggestions for future improvements

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.

References

[1] P.K. Agarwal, H. Edelsbrunner, and O. Schwarzkopf, Euclidean minimum spanning tree and bichromatic closest pairs, and E. Welzl, Discrete Comput. Geom. 6 (1991), 407--422.

[2] P.K. Agarwal and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Comput. Geom. Theory & Appl. 1 (1991), 65--78.

[3] P.K. Agarwal and B. Aronov, Counting facets and incidences, Discrete Comput. Geom. 7 (1992), 359--369.

[4] P.K. Agarwal, J. Matou\v{s}ek, and S. Suri, Farthest neighbors, maximum spanning trees and related problems in higher dimensions, Comput. Geom. Theory & Appl. 1 (1992), 189--201.

[5] P.K. Agarwal, M. van Kreveld, and M. Overmars, Intersection queries in sets of discs, BIT 32 (1992), 268--279.

[6] P.K. Agarwal and J. Matou\v{s}ek, Relative neighborhood graphs in three dimensions, Comput. Geom. Theory & Appl. 2 (1992), 1--15.

[7] P.K. Agarwal and M. Sharir, Applications of a new space partitioning technique, Discrete Comput. Geom. 9 (1993), 11--38.

[8] P.K. Agarwal and M. Sharir, Circle shooting in a simple polygon, J. Algorithms 14 (1993), 68--87.

[9] P.K. Agarwal and M. Sharir, Circular visibility of a simple polygon >from a fixed point, Int. J. Comput. Geom. Appls. 3 (1993), 1--25.

[10] P.K. Agarwal, B. Aronov, M. Sharir, and S. Suri, Selecting distances in the plane, Algorithmica 9 (1993), 495--514.

[11] P.K. Agarwal, M. Pellegrini, and M. Sharir, Counting circular arc intersections, SIAM J. Comput 22 (1993), 778--793.

[12] P.K. Agarwal and J. Matou\v{s}ek, Ray shooting and parametric search, SIAM J. Comput 22 (1993), 794--806.

[13] P.K. Agarwal, M. van Kreveld and M. Overmars, Intersection queries in curved objects, J. Algorithms 15 (1993), 229--266.

[14] P.K. Agarwal, A. Efrat, M. Sharir, and S. Toledo, Computing a Segment-Center for a planar point set, J. Algorithms 15 (1993), 314--323.

[15] P.K. Agarwal and M. Sharir, Planar geometric location problems, Algorithmica 11 (1994), 185--195.

[16] P.K. Agarwal and J. Matou\v{s}ek, Range searching P.K. Agarwal semialgebraic sets, Discrete Comput. Geom. 11 (1994), 393--418.

[17] P.K. Agarwal, N. Alon, B. Aronov, and S. Suri, Can visibility graphs be represented compactly? Discrete Comput. Geom. 12 (1994), 347--365.

[18] P.K. Agarwal and J. Matou\v{s}ek, Dynamic half-space searching and its applications, Algorithmica 14 (1995), 325--345.

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

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

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

[22] S. Cappell, J. E. Goodman, J. Pach, R. Pollack, M. Sharir, and R. Wenger, Common tangents and common transversals, Advances in Math. 104 (1994), 198--215.

[23] J. E. Goodman, R. Pollack, and R. Wenger, Geometric Transversal Theory, in New Trends in Discrete and Computational Geometry J. Pach Ed. (1963), 163--198.

[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, Discrete Comput. Geom. 13, (1995), 469--476.

[25] J. E. Goodman, R. Pollack, and R. Wenger, There are uncountably many universal topological planes, Geom. Dedicata l59, (1996), 157--162.

[26] J. E. Goodman, R. Pollack, and R. Wenger, Bounding the number of geometric permutations induced by k-transversals, J. Combinatorial Theory Ser. A to appear.

[27] J. E. Goodman, R. Pollack, R. Wenger, and T. Zamfirescu, Every arrangement extends to a spread, Combinatorica 14, (1994), 301--306.

[28] J. E. Goodman, R. Pollack, R. Wenger, and T. Zamfirescu, Arrangements and topological planes, Amer. Math. Monthly 101, (1994), 866--878.

[29] N.E. Mn\"ev, On manifolds of combinatorial types of projective configurations and convex polyhedra, Sov. Math. Dokl. 32, (1985).

[30] N.E. Mn\"ev, The universality theorems of the classification problem of configuration varieties and convex polytope varieties in Topology and Geometry--Rokhlin Seminar, Lecture Notes in Mathematics 1346 (1988).

[31] N. Mn\"ev, The universality theorem on the oriented matroid stratification of the space of real matrices, in Discrete and Computational Geometry:Papers from the DIMACS special year} (J.E. Goodman, R. Pollack and W. Steiger, Eds. DIMACS series 6, Amer. Math. Soc., (1991), 237--243.

[32] P. Shor, Stretchability of pseudolines is NP-hard, in Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift DIMACS series 4, Amer. Math. Soc., (1991), 531--554.

[33] R. Pollack and M.-F. Roy, On the number of cells defined by a set of polynomials, Compte Rendus 316, (1993), 573--577.

[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 Algorithmic Foundations of Robotics (K.Y. Goldberg, D. Halperin, J.-C. Latombe, R.H. Wilson, Eds.) A.K. Peters, (1995), 537--555.

[35] S. Basu, R. Pollack and M.-F. Roy, On the number of cells defined by a family of polynomials on a variety, Mathematika 43, (1996), 120--126.

[36] S. Basu, R. Pollack and M.-F. Roy, On the combinatorial and algebraic complexity of Quantifier Elimination, in Proc. 34th IEEE Symp. on Foundations of Computer Science (1994) 632--641.

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

[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 Quantifier Elimination and Cylindrical Algebraic Decomposition (B. Caviness and J. Johnson Eds.), Springer-Verlag, (1996).

[39] Computing Roadmaps of Semi-algebraic Sets (Extended Abstract),in Twenty-Eighth ACM Symp. on Theory of Computing (1996), 168--173.

[40] S. Basu, R. Pollack and M.-F. Roy, Computing Roadmaps of Semi-algebraic Sets on a Variety (Extended Abstract) in Foundations of Computational Mathematics: Proceedings of a Conference held at IMPA, Rio de Janeiro, from 5 to 12 of January 1997 Springer-Verlag, to appear.

[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, Jounal of Complexity to appear.

[42] V. Capoyleas and J. Pach, A Tur\'an-type theorem on chords of a convex polygon, J. Comb. Th. Ser. B 56 (1992), 9--15.

[43] J. Pach and J. T\"or\H ocsik, Layout of rooted trees, in Planar Graphs (W.T. Trotter, ed.), DIMACS Series, 9, Amer. Math. Soc., Providence, 1993, 131--137.

[44] Y. Ikebe, M. Perles, A. Tamura, and S. Tokunaga, The rooted tree embedding problem into points in the plane, Discrete Comput. Geom. 11 (1994), 51--63.

[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 Eleventh ACM Symp. Comp. Geom. (1995), 147--151

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

[48] Perles, M.A., and Prabhu, N., A Property of Graphs of Convex Polytopes, Journal of Combinatorial Theory - Series A 62, (1994) 155 -- 157.

[49] Perles, M.A. and Prabhu, N., Transversals of Polytopes, Israel Journal of Mathematics to appear.

[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, Discrete Comput. Geom. 6, (1991), 435--442.

[51] B. Aronov and P.K. Agarwal, Counting facets and incidences, Discrete Comput. Geom. 7, (1992) 359--369.

[52] B. Aronov, H.~Edelsbrunner, L. Guibas, and M. Sharir, The number of edges of many faces in a line segment arrangement, Combinatorica 12, (1992) 261--274.

[53] B. Aronov and J. O'Rourke, Nonoverlap of the star unfolding, Discrete Comput. Geom. 8 (1993), 219--250.

[54] B. Aronov, R. Seidel and D. Souvaine, Compatible triangulations, Computational Geometry: Theory and Applications 3 (1993) 27--35.

[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, Combinatorica 14 (1994) 127--134.

[56] P. Agarwal, N. Alon, B. Aronov, and S. Suri, Can visibility graphs be represented compactly? Discrete Comput. Geom. 12 (1994) 347--365.

[57] B. Aronov and J. Matou\v{s}ek, On stabbing triangles by lines in 3-space, Comment. Math. Univ. Carolinae 36, (1995) 109--113.

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

[59] J. Richter-Gebert and G. Ziegler, Realization spaces of 4-polytopes are Universal, Bull. Amer. Math. Soc. 32 (1995), 403--412.

[60] H. Guenzel, The universal partition theorem for oriented matroids, Discrete Comput. Geom. 15 (1996) 121--145.

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

APPENDIX TO SEPTEMBER, 1996 REPORT


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.

  1. 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.

  2. 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.

  3. 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 .

  4. 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.

    It was while at DIMACS that I was able to make several important connections between work begun earlier on stress and rigidity, and certain metrical properties of polytopes, such as volume and the Brunn-Minkowski Theorem. This led to a very satisfactory theory of generalized stress, with a direct relationship to McMullen's polytope algebra and new proof of the g-Theorem.

  5. 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.

One of the goals of DIMACS was to bring together a group of researchers with diverse but overlapping interests in a supportive environment which could foster productive interchange and new ideas and directions for research, with long-term impact. Speaking personally, I cannot imagine how DIMACS could have met this goal better than it did.
DIMACS home page
Contacting the Center
Document last modified on May 1, 1998.