ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk 5/3 ) , on the complexity of the k th level in an arrangement of n planes in R 3 , or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is $O(n\sqrt{k}\alpha(n/k))$ , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n 2 k 5/6 α(n/k)) . 〈lsiheader〉 〈onlinepub〉26 June, 1998 〈editor〉Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; 〈pdfname〉19n3p315.pdf 〈pdfexist〉yes 〈htmlexist〉no 〈htmlfexist〉no 〈texexist〉yes 〈sectionname〉 〈/lsiheader〉
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009348
