--- _id: '4074' abstract: - lang: eng text: We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given. acknowledgement: The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from the NCRD, the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988. article_processing_charge: No article_type: original author: - first_name: Kenneth full_name: Clarkson, Kenneth last_name: Clarkson - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 - first_name: Leonidas full_name: Guibas, Leonidas last_name: Guibas - first_name: Micha full_name: Sharir, Micha last_name: Sharir - first_name: Emo full_name: Welzl, Emo last_name: Welzl citation: ama: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. 1990;5(1):99-160. doi:10.1007/BF02187783 apa: Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187783 chicago: Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187783. ieee: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” Discrete & Computational Geometry, vol. 5, no. 1. Springer, pp. 99–160, 1990. ista: Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. 5(1), 99–160. mla: Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” Discrete & Computational Geometry, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:10.1007/BF02187783. short: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete & Computational Geometry 5 (1990) 99–160. date_created: 2018-12-11T12:06:47Z date_published: 1990-03-01T00:00:00Z date_updated: 2022-02-17T15:41:04Z day: '01' doi: 10.1007/BF02187783 extern: '1' intvolume: ' 5' issue: '1' language: - iso: eng main_file_link: - url: https://link.springer.com/article/10.1007/BF02187783 month: '03' oa_version: None page: 99 - 160 publication: Discrete & Computational Geometry publication_identifier: eissn: - 1432-0444 issn: - 0179-5376 publication_status: published publisher: Springer publist_id: '2048' quality_controlled: '1' status: public title: Combinatorial complexity bounds for arrangements of curves and spheres type: journal_article user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17 volume: 5 year: '1990' ...