Abstract
Order types are a means to characterize the combinatorial properties of a finite point configuration. In particular, the crossing properties of all straight-line segments spanned by a planar n-point set are reflected by its order type. We establish a complete and reliable data base for all possible order types of size n=10 or less. The data base includes a realizing point set for each order type in small integer grid representation. To our knowledge, no such project has been carried out before.
We substantiate the usefulness of our data base by applying it to several problems in computational and combinatorial geometry. Problems concerning triangulations, simple polygonalizations, complete geometric graphs, and k-sets are addressed. This list of applications is not meant to be exhaustive. We believe our data base to be of value to many researchers who wish to examine their conjectures on small point configurations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aichholzer, O.: The path of a triangulation, in Proc. 15th Ann. ACM Sympos. Computational Geometry, Miami Beach, USA, 1999, pp. 14-23.
Aichholzer, O., Aurenhammer, F. and Krasser, H.: Enumerating order types for small point sets with applications, In: Proc. 17th Ann. ACM Sympos. Computational Geometry, Medford, USA, 2001, pp. 11-18.
Aichholzer, O., Aurenhammer, F., Hurtado, F. and Krasser, H.: Towards compatible triangulations, In: Proc. 7th Ann. Int. Computing and Combinatorics Conf. CoCOON-2001, Guilin, China, Lecture Notes in Comput. Sci. 2108, Springer, New York, 2001, pp. 101–110. To appear in Theoret. Comput. Sci.
Aichholzer, O., Hurtado, F. and Noy, M.: On the number of triangulations every planar point set must have, In: Proc. 13th Ann. Canadian Conference on Computational Geometry CCCG 2001, Waterloo, Canada, 2001, pp. 13-16.
Aichholzer, O. and Krasser, H.: The point set order type data base: A collection of applications and results, In: Proc. 13th Ann. Canadian Conference on Computational Geometry CCCG 2001, Waterloo, Canada, 2001, pp. 17-20.
Arkin, E., Fekete, S., Hurtado, F., Mitchell, J., Noy, M., Sacristán, V. and Sethia, S.: On the reflexivity of point sets, In: Proc. 10th Ann. Fall Workshop on Computational Geometry, Stony Brook, NY, 2000.
Aronov, B., Seidel, R. and Souvaine, D.: On compatible triangulations of simple polygons, Comput. Geom. 3 (1993), 27–35.
Aurenhammer, F.: Voronoi diagrams-a survey of a fundamental geometric data structure, ACM Comput. Surveys 23 (1991), 345–405.
Aronov, B., Erdös, P., Goddard, W., Kleitman, D. J., Klugerman, M., Pach, J. and Schulman, L. J.: Crossing families, Combinatorica 14 (1994), 127–134.
Avis, D. and Fukuda, K.: Reverse search for enumeration, Discrete Appl. Math. 65 (1996), 618–632.
Björner, A., Las Vergnas, M., Sturmfels, B., White, N. and Ziegler, G.: Oriented Matroids, Cambridge Univ. Press, 1993.
Bokowski, J. and Guedes de Oliveira, A.: On the generation of oriented matroids, Discrete Comput. Geom. 24 (2000), 197–208.
Brodsky, A., Durocher, S. and Gether, E.: The rectilinear crossing number of K 10 is 62, Electron. J. Combinatorics 8 (2001), Research Paper 23.
de Berg, M., van Krefeld, M., Overmars, M. and Schwarzkopf, O.: Computational Geometry-Algorithms and Applications, Springer, Berlin, 1997.
Dey, T. K.: Improved bounds for planar k-sets and related problems, Discrete Comput. Geom. 19 (1998), 373–382.
Erdös, P. and Guy, R. K.: Crossing number problems, Amer. Math. Monthly 88 (1973), 52–58.
Felsner, S.: On the number of arrangements of pseudolines, Discrete Comput. Geom. 18 (1997), 257–267.
Finschi, L. and Fukuda, K.: Generation of oriented matroids-a graph theoretical approach, Discrete Comput. Geom. 27 (2002), 117–136.
Galtier, J., Hurtado, F., Noy, M., Perennes, S. and Urrutia, J.: Simultaneous edge flipping in triangulations, Manuscript, Universitat Politecnica de Catalunya, Barcelona, Spain, 2000. http://www-ma2.upc.es/~hurtado/flipcorner.html
García, A., Noy, M. and Tejel, J.: Lower bounds on the number of crossing-free subgraphs of K N, Comput. Geom. 16 (2000), 211–221.
Goodman, J. E.: Pseudoline arrangements, In: J. E. Goodman and J. O'Rourke (eds), Handbook of Discrete and Computational Geometry, CRC Press LLC, Boca Raton, NY, 1997.
Goodman, J. E. and Pollack, R.: Multidimensional sorting, SIAM J. Comput. 12 (1983), 484–507.
Goodman, J. E., Pollack, R. and Sturmfels, B.: Coordinate representation of order types requires exponential storage, In: Proc. 21st Ann. ACM Sympos. Theory of Computing, 1989, pp. 405-410.
Hayward, R. B.: A lower bound for the optimal crossing-free Hamiltonian cycle problem, Discrete Comput. Geom. 2 (1987), 327–343.
Kranakis, E. and Urrutia, J.: Isomorphic triangulations with small number of Steiner points, Intertat. J. Comput. Geom. Appl. 9 (1999), 171–180.
Krasser, H.: Kompatible Triangulierungen ebener Punktmengen, MS thesis, IGI-TU Graz, Austria, 1999.
Saalfeld, A.: Joint triangulations and triangulation maps, In: Proc. 3rd Ann. ACM Sympos. Computational Geometry, Waterloo, Canada, 1987, pp. 195-204.
Santos, F. and Seidel, R.: A better bound on the number of triangulations of a planar point set, Manuscript, 2000.
Tóth, G. and Valtr, P.: Note on Erdös-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457–459.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Aichholzer, O., Aurenhammer, F. & Krasser, H. Enumerating Order Types for Small Point Sets with Applications. Order 19, 265–281 (2002). https://doi.org/10.1023/A:1021231927255
Issue Date:
DOI: https://doi.org/10.1023/A:1021231927255