The number of edges of many faces in a line segment arrangement |
| |
Authors: | B Aronov H Edelsbrunner L J Guibas M Sharir |
| |
Institution: | (1) DIMACS Center, Rutgers University, 08855 Piscataway, New Jersey, U.S.A.;(2) Present address: Department of Computer Science, Polytechnic University, 11201 Brooklyn, NY, U.S.A.;(3) Computer Science Department, Stanford University, and DEC Systems Research Center, 94301 Paolo Alto, California, U.S.A.;(4) Department of Computer Science, University of Illinois at Urbana-Champaign, 61801 Urbana, Illinois, U.S.A.;(5) School of Mathematical Sciences, Tel Aviv University, Tel Aviv, Israel;(6) Courant Institute of Mathematical Sciences, New York University, 10012 New York, U.S.A. |
| |
Abstract: | We show that the maximum number of edges boundingm faces in an arrangement ofn line segments in the plane isO(m
2/3
n
2/3+n(n)+nlogm). This improves a previous upper bound of Edelsbrunner et al. 5] and almost matches the best known lower bound which is (m
2/3
n
2/3+n(n)). In addition, we show that the number of edges bounding anym faces in an arrangement ofn line segments with a total oft intersecting pairs isO(m
2/3
t
1/3+n(t/n)+nmin{logm,logt/n}), almost matching the lower bound of (m
2/3
t
1/3+n(t/n)) demonstrated in this paper.Work on this paper by the first and fourth authors has been partially supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484. Work by the first author has also been supported by an AT&T Bell Laboratories Ph.D. scholarship at New York University and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center (NSF-STC88-09648). Work by the second author has been supported by NSF under Grants CCR-87-14565 and CCR-89-21421. Work by the fourth author has additionally been supported by grants from the U.S.-Israeli Binational Science Foundation, the NCRD (the Israeli National Council for Research and Development) and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli National Academy of Sciences. |
| |
Keywords: | 52 B 05 52 C 10 68 U 05 |
本文献已被 SpringerLink 等数据库收录! |
|