Combinatorial complexity bounds for arrangements of curves and surfaces
- 1 January 1988
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 568-579
- https://doi.org/10.1109/sfcs.1988.21973
Abstract
The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest.Keywords
This publication has 18 references indexed in Scilit:
- Implicitly representing arrangements of lines or segmentsPublished by Association for Computing Machinery (ACM) ,1988
- The complexity of many faces in arrangements of lines of segmentsPublished by Association for Computing Machinery (ACM) ,1988
- Algorithms in Combinatorial GeometryPublished by Springer Science and Business Media LLC ,1987
- Constructing Arrangements of Lines and Hyperplanes with ApplicationsSIAM Journal on Computing, 1986
- On the maximal number of edges of many faces in an arrangementJournal of Combinatorial Theory, Series A, 1986
- Extremal problems in discrete geometryCombinatorica, 1983
- On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometryCombinatorica, 1983
- On some problems of elementary and combinatorial geometryAnnali di Matematica Pura ed Applicata (1923 -), 1975
- A theorem on arrangements of lines in the planeIsrael Journal of Mathematics, 1969
- On Sets of Distances of n PointsThe American Mathematical Monthly, 1946