Abstract
The allowable sequence associated to a configuration of points was first developed by the authors in order to investigate what combinatorial structure lay behind the Erdős-Szekeres conjecture (that any 2n-2 + 1 points in general position in the plane contain among them n points which are in convex position). Though allowable sequences did not lead to any progress on this ancient problem, there did emerge an object that had considerable intrinsic interest, that turned out to be related to some other well-studied structures such as pseudoline arrangements and oriented matroids, and that had as well a combinatorial simplicity and suggestiveness which turned out to be effective in the solution of several other classical problems. These connections and applications are discussed in Sections 2, 3, and 4 of this paper.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
N. Alon: The number of polytopes, configurations, and real matroids. Mathematika 33 (1986) 62–71
N. Alon and E. Györi: The number of small semispaces of a finite set of points in the plane. J. Comb. Theory, Ser. A 41 (1986) 154–157
B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir and R. Wenger: Points and triangles in the plane and halving planes in space. Discrete Comput. Geom. 6 (1991) 435–442
B. Aronov, J. E. Goodman, R. Pollack and R. Wenger: Hadwiger’s theorem for line transversals does not generalize to higher dimensions. Unpublished manuscript, 1989
I. Bárány, Z. Füredi and L. Lovász: On the number of halving planes. In: Proc. Fifth Annual ACM Sympos. on Computational Geometry. 1989, pp. 140–144
A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler: Oriented Matroids. Cambridge Univ. Press, Cambridge 1992
R. G. Bland and M. Las Vergnas: Orientability of Matroids. J. Comb. Theory, Ser. B 23 (1978) 94–123
J. Bokowski, J. Richter and B. Sturmfels: Nonrealizability proofs in computational geometry. Discrete Comput. Geom. 5 (1990) 333–350
J. Bokowski and B. Sturmfels: Oriented matroids and chirotopes—problems of geometric realizability. TH Darmstadt, 1985
J. Bokowski and B. Sturmfels: On the coordinatization of oriented matroids. Discrete Comput. Geom. 1 (1986) 293–306
J. Bokowski and B. Sturmfels: Computational Synthetic Geometry. Lecture Notes in Mathematics, vol. 1355. Springer, Berlin Heidelberg 1989
E. Boros and Z. Fiiredi: The number of triangles covering the center of an n-set. Geometriae Dedicata 17 (1984) 69–77
G. R. Burton and G. B. Purdy: The directions determined by n points in the plane. J. London Math. Soc. (2) 20 (1979) 109–114
R. J. Canham: Arrangements of hyperplanes in projective and Euclidean spaces. University of East Anglia, Norwich 1971
S. E. Cappell, J. E. Goodman, J. Pach, R. Pollack, M. Sharir and R. Wenger: The Combinatorial Complexity of Hyperplane Transversals. Adv. Math., to appear
V. Chvátal and G. Klincsek: Finding largest convex subsets. Cong. Num. 29 (1980) 453–460
K. L. Clarkson and P. W. Shor: Applications of random sampling, II. Discrete Comput. Geom. 4 (1989) 387–421
R. Cordovil: Sur les matroïdes orientés de rang trois et les arrangements de pseudodroites dans le plan projectif reél. European J. Comb. 3 (1982) 307–318
R. Cordovil: Oriented matroids and geometric sorting. Canad. Math. Bull. 26 (1983) 351–354
L. Danzer, B. Griinbaum and V. Klee: Helly’s Theorem and its Relatives. In: Convexity. Proc. Sympos. Pure Math., Vol. 7, (1963) pp. 100–181. Amer. Math. Soc., Providence
D. Dobkin and D. Silver: Recipes for geometry and numerical analysis, Part 1: an empirical study. In: Proc. Fourth Annual ACM Sympos. on Computational Geometry, 1988, pp. 93–105
A. Dreiding, A. Dress and A. Haegi: Classification of Mobile Molecules by Category Theory. Studies in Physical and Theoretical Chemistry 23 (1982) 39–58
A. Dreiding and K. Wirth: Classification of Finite Ordered Point Sets in Oriented d-Dimensional Space. Math. Chemistry 8 (1980) 341–352
A. Dress: Chirotopes and Oriented Matroids. Bayr. Math. Schriften 21 (1986) 14–68
P. Edelman: On the average number of k-sets. Discrete Comput. Geom. 8 (1992) 209–213
P. Edelman and C. Greene: Combinatorial correspondences for Young tableaux, balanced tableaux and maximal chains in the Bruhat order of In: Combinatorics and Contemporary Math., vol. 34. Amer. Math. Soc., Providence 1984, pp. 42–99
H. Edelsbrunner: Algorithms in Combinatorial Geometry. Springer, Berlin 1987
H. Edelsbrunner, J. O’Rourke and R. Seidel: Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput 15 (1986) 341–363
H. Edelsbrunner and E. Welzl: On the number of line-separations of a finite set in the plane. J. Comb. Theory, Ser. A 38 (1985) 15–29
P. Erdös, L. Lovász, A. Simmons and E. G. Strauss: Dissection graphs of planar point sets. In: A Survey of Combinatorial Theory. North-Holland, Amsterdam 1973, pp. 139–149
J. Folkman and J. Lawrence: Oriented Matroids. J. Combin. Theory, Ser. B 25 (1978) 199–236
S. Fortune: Stable maintenance of point-set triangulation in two dimensions. In: Proc. 30th Annual IEEE Sympos. on the Foundations of Computer Science, 1989, pp. 494–499
S. Fortune and V. Milenkovic: Numerical stability of algorithms for line arrangements. In: Proc. Seventh Annual ACM Sympos. on Computational Geometry, 1991, pp. 334–341
M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York 1979
J. E. Goodman: Proof of a conjecture of Burr, Grünbaum, and Sloane. Discrete Math. 32 (1980) 27–35
J. E. Goodman and R. Pollack: On the combinatorial classification of non-degenerate configurations in the plane. J. Comb. Theory, Ser. A 29 (1980) 220–235
J. E. Goodman and R. Pollack: Proof of Grünbaum’s conjecture on the stretchability of certain arrangements of pseudolines. J. Comb. Theory, Ser. A 29 (1980) 385–390
J. E. Goodman and R. Pollack: Convexity theorems for generalized planar configurations. In: Proc. of the Conf. on Convexity and Related Combinatorial Geometry, Univ. of Okla., 1980. Marcel Dekker, New York 1982, pp. 73–80
J. E. Goodman and R. Pollack: Helly-type theorems for pseudoline arrangements in P 2. J. Comb. Theory, Ser. A 32 (1982) 1–19
J. E. Goodman and R. Pollack: A theorem of ordered duality. Geometriae Dedicata 12 (1982) 63–72
J. E. Goodman and R. Pollack: Multidimensional Sorting. SIAM J. Comput. 12 (1983) 484–507
J. E. Goodman and R. Pollack: Isotopy problem for configurations. In: List of Problems, Tagungsbericht Oberwolfach. Tagung fiber kombinatorische Geometrie. September 1984
J. E. Goodman and R. Pollack: On the number of k-subsets of a set of n points in the plane. J. Comb. Theory, Ser. A 36 (1984) 101–104
J. E. Goodman and R. Pollack: Polynomial realization of pseudoline arrangements. Comm. Pure Appl. Math. 38 (1984) 725–732
J. E. Goodman and R. Pollack: Semispaces of configurations, cell complexes of arrangements. J. Comb. Theory, Ser. A 37 (1984) 257–293
J. E. Goodman and R. Pollack: A combinatorial version of the isotopy conjecture. In: Discrete Geometry and Convexity. Ann. New York Acad. Sci., 1985, pp. 12–19
J. E. Goodman and R. Pollack: Upper bounds for configurations and polytopes in Rd. Discrete Comput. Geom. 1 (1986) 219–227
J. E. Goodman and R. Pollack: Hadwiger’s Transversal Theorem in Higher Dimensions. J. Amer. Math. Soc. 1 (1988) 301–309
J. E. Goodman, R. Pollack and B. Sturmfels: Coordinate representation of order types requires exponential storage. In: Proc. 21st Annual ACM Sympos. on the Theory of Computing 1989, pp. 405–410
J. E. Goodman, R. Pollack and B. Sturmfels: The Intrinsic Spread of a Configuration in Rd. J. Amer. Math. Soc. 3 (1990) 639–651
J. E. Goodman, R. Pollack and R. Wenger: Geometric Transversal Theory. In: Recent Advances in Discrete and Computational Geometry. Springer, Berlin Heidelberg 1991. This volume, pp. 163–198
D. H. Greene and F. F. Yao: Finite-resolution computational geometry. In: Proc. 27th Annual IEEE Sympos. on the Foundations of Computer Science 1986, pp. 143–152
D. Yu. Grigor’ev and N. N. Vorobjov: Solving systems of polynomial inequalities in subexponential time. J. Symbolic Corn. 5 (1988) 37–64
B. Grünbaum: Arrangements and Spreads. Amer. Math. Soc., Providence 1972
L. Guibas, D. Salesin and J. Stolfi: Epsilon geometry: building robust algorithms from imprecise computations. In: Proc. Fifth Annual ACM Sympos. on Computational Geometry, 1989, pp. 208–217
H. Hadwiger: Uber Eibereiche mit gemeinsamer Treffgeraden. Portugal. Math. 16 (1957) 23–29
E. Halsey: Zonotopal complexes on the d-cube. University of Washington, Seattle 1971
E. Helly: Uber Mengen Konvexer Körper mit Gemeinschaftlichen Punkten. Jber. Deutsch. Math. Verein 32 (1923) 175–176
C. Hoffman: The problems of accuracy and robustness in geometric computation. Computer 22 (1989) 31–42
J. Hoperoft and P. Kahn: A paradigm for robust geometric algorithms. Technical Report TR 89–1044, Cornell University 1989
M. Iri and K. Sugihara: Geometric algorithms in finite precision arithmetic. Technical Report RMI 88–10, University of Tokyo 1988
M. Iri and K. Sugihara: Construction of the Voronoi diagram for one million generators in single precision arithmetic. First Canadian Conference on Computational Geometry, 1989
B. Jaggi, P. Mani-Levitska, N. White and B. Sturmfels: Uniform oriented matroids without the isotopy property. Discrete Comput. Geom. 4 (1989) 97100
R. E. Jamison: Structure of slope critical configurations. Geometriae Dedicata 16 (1984) 249–277
R. E. Jamison: A survey of the slope problem. In: Discrete Geometry and Convexity. Ann. New York Acad. Sci., 1985, pp. 34–51
R. E. Jamison and D. Hill: A catalogue of sporadic slope-critical configurations. Cong. Num. 40 (1983) 101–125
G. Kalai: Many triangulated spheres. Discrete Comput. Geom. 3 (1988) 1–14
M. Katchalski: Thin Sets and Common Transversals. J. Geom. 14 (1980) 103–107
P. Kirchberger: Über Tschebyschefsche Annáherungsmethoden. Math. Ann. 57 (1903) 509–540
M. Klawe, M. Paterson and N. Pippenger: Inversions with \( n^{1 + \Omega (1 + \sqrt {\log n)} } \) transpositions at the median. Unpublished manuscript, 1982
V. Klee: The number of vertices of a convex polytope. Canad. J. Math. 16 (1964) 701–720
M. Las Vergnas: Order properties of lines in the plane and a conjecture of G. Ringel. J. Comb. Theory, Ser. B 41 (1986) 246–249
F. Levi: Die Teilung der projectiven Ebene durch Gerade oder Pseusogerade. Ber. Math. -Phys. Kl. sáchs. Akad. Wiss. Leipzig 78 (1926) 256–267
L. Lovász: On the number of halving lines. Ann. Univ. Sci. Budapest, Eötvös, Sect. Math. 14 (1971) 107–108
P. McMullen: The maximum number of faces of a convex polytope. Mathematika 17 (1970) 179–184
V. Milenkovic: Verifiable implementations of geometric algorithms using finite precision arithmetic. Artificial Intelligence 37 (1988) 377–401
V. Milenkovic: Double precision geometry: a general technique for calculating line and segment intersections using rounded arithmetic. In: Proc. 30th Ann. IEEE Sympos. on the Foundations of Computer Science, 1989
V. Milenkovic and L. R. Nackman: Finding compact coordinate representations for polygons and polyhedra. In: Proc. Sixth Annual ACM Sympos. on Computational Geometry 1990, pp. 244–259
J. Milnor: On the Betti numbers of real varieties. Proc. Amer. Math. Soc. 15 (1964) 275–280
N. E. Mnëv: On manifolds of combinatorial types of projective configurations and convex polyhedra. Soviet Math. Dokl. 32 (1985) 335–337
N. E. Mnëv: The universality theorems on the classification problem of configuration varieties and convex polytope varieties. In: Topology and Geometry-Rokhlin Seminar, Lecture Notes in Mathematics, vol. 1346. Springer, Berlin Heidelberg, 1988, pp. 527–543
D. J. Newman: Efficient co-monotone approximation. J. Approx. Theory 25 (1979) 189–192
J. Pach, W. Steiger and E. Szemerédi: An upper bound on the number of planar k-sets. In: Proc. 30th Ann. IEEE Sympos. on the Foundations of Computer Science 1989, pp. 72–79
G. W. Peck: On k-sets in the plane. Discrete Math. 56 (1985) 73–74
R. Perrin: Sur le probléme des aspects. Bull. Soc. Math. France 10 (1881) 103–127
R. Pollack and R. Wenger: A family of generalizations of Hadwiger’s theorem to hyperplane transversals. Unpublished manuscript
R. Pollack and R. Wenger: Necessary and sufficient conditions for hyperplane transversals. Combinatorica 10 (1990) 307–311
G. Ringel: Teilungen der projectiven Ebene durch Geraden oder topologische Geraden. Math. Z. 64 (1956) 79–102
S. Sahni: Quadratic Programming is NP-hard. SIAM J. Computing 3 (1974) 262–279
P. R. Scott: On the sets of directions determined by n points. Amer. Math. Monthly 77 (1970) 502–505
M. Sharir: On k-sets in arrangements of curves and surfaces. Discrete Comput. Geom. 6 (1991) 593–613
P. W. Shor: Stretchability of pseudoline arrangements is NP-hard. In: Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, American Math. Soc., Providence 1991, pp. 531–554
R. Stanley: On the number of reduced decompositions of elements of Coxeter groups. Europ. J. Combinatorics 5 (1984) 359–372
J. Steiner: Einige Gesetze fiber die Teilung der Ebene und des Raumes. J. Reine Angew. Math. 1 (1826) 349–364
B. Sturmfels: Computational Synthetic Geometry. Ph. D. dissertation, University of Washington, Seattle 1987
P. Suvorov: Isotopic but not rigidly isotopic plane systems of straight lines. In: Topology and Geometry—Rokhlin Seminar, Lecture Notes in Mathematics, 1346. Springer, Berlin Heidelberg 1988, pp. 545–555
R. Thom: Sur l’homologie des variétés algébriques réelles. In: Differential and Combinatorial Topology, Princeton University Press, Princeton 1965, pp. 255–265
P. Ungar: 2N noncollinear points determine at least 2N directions. J. Comb. Theory, Ser. A 33 (1982) 343–347
S. T. Vrećica and R. T. Živaljevié: The colored Tverberg’s problem and complexes of injective functions, to appear
H. E. Warren: Lower bounds for approximation of nonlinear manifolds. Trans. Amer. Math. Soc. 133 (1968) 167–178
E. Welzl: More on k-sets of finite sets in the plane. Discrete Comput. Geom. 1 (1986) 95–100
R. Wenger: A Generalization of Hadwiger’s Theorem to Intersecting Sets. Discrete Comput. Geom. 5 (1990) 383–388
R. Wenger: Geometric Permutations and Connected Components. Technical report TR-90–50, DIMACS 1990
N. White: A nonuniform matroid which violates the isotopy conjecture. Discrete Comput. Geom. 4 (1989) 1–2
T. Zaslaysky: Facing Up to Arrangements: Face Count Formulas for Partitions of Space by Hyperplanes. Memoirs Amer. Math. Soc. (1), 154 Amer. Math. Soc., Providence 1975
T. Zaslaysky: Bilateral Geometries. Unpublished manuscript, 1980
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Goodman, J.E., Pollack, R. (1993). Allowable Sequences and Order Types in Discrete and Computational Geometry. In: Pach, J. (eds) New Trends in Discrete and Computational Geometry. Algorithms and Combinatorics, vol 10. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-58043-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-642-58043-7_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55713-5
Online ISBN: 978-3-642-58043-7
eBook Packages: Springer Book Archive