ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Let \C be a collection of n Jordan regions in the plane in general position, such that each pair of their boundaries intersect in at most s points, where s is a constant. If the boundaries of two sets in \C cross exactly twice, then their intersection points are called regular vertices of the arrangement \A(\C) . Let R(\C) denote the set of regular vertices on the boundary of the union of \C . We present several bounds on |R(\C)| , depending on the type of the sets of \C . (i) If each set of \C is convex, then |R(\C)|=O(n 1.5+\eps ) for any \eps〉0 . (ii) If no further assumptions are made on the sets of \C , then we show that there is a positive integer r that depends only on s such that |R(\C)|=O(n 2-1/r ) . (iii) If \C consists of two collections \C 1 and \C 2 where \C 1 is a collection of m convex pseudo-disks in the plane (closed Jordan regions with the property that the boundaries of any two of them intersect at most twice), and \C 2 is a collection of polygons with a total of n sides, then |R(\C)|=O(m 2/3 n 2/3 +m +n) , and this bound is tight in the worst case.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s00454-001-0001-7
Permalink
