id: 00764225
dt: j
an: 00764225
au: Arkin, E.M.; Halperin, D.; Kedem, K.; Mitchell, J.S.B.; Naor, N.
ti: Arrangements of segments that share endpoints: Single face results.
so: Discrete Comput. Geom. 13, No.3-4, 257-270 (1995).
py: 1995
pu: Springer-Verlag, New York, NY
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/BF02574043
ab: Summary: We provide new combinatorial bounds on the complexity of a face in
    an arrangement of segments in the plane. In particular, we show that
    the complexity of a single face in an arrangement of $n$ line segments
    determined by $h$ endpoints is $O(h\log h)$. While the previous upper
    bound, $O(nα(n))$, is tight for segments with distinct endpoints, it
    is far from being optimal when $n= Ω(h^2)$. Our results show that, in
    a sense, the fundamental combinatorial complexity of a face arises not
    as a result of the number of segments, but rather as a result of the
    number of endpoints.
rv: