Authors
Citation
M. Sharir, EXCESS IN ARRANGEMENTS OF SEGMENTS, Information processing letters, 58(5), 1996, pp. 245-247
Citations number
6
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
ISSN journal
00200190
Volume
58
Issue
5
Year of publication
1996
Pages
245 - 247
Database
ISI
SICI code
0020-0190(1996)58:5<245:EIAOS>2.0.ZU;2-R
Abstract
Let S be a set of n line segments in the plane. The excess of S is the
number of repetitions of segments of S along the boundary of the same
face of A(S), summed over all segments and faces. We show that the ex
cess of S is at most O(n log log n), improving a previous O(n log n) b
ound given by Aronov and Sharir (1994).