Arrangements of segments that share endpoints: Single face results

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 ²). 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.