ON DISJOINT CONCAVE CHAINS IN ARRANGEMENTS OF (PSEUDO) LINES (VOL 40,PG 189, 1991)

Authors
HALPERIN D SHARIR M
Citation
D. Halperin et M. Sharir, ON DISJOINT CONCAVE CHAINS IN ARRANGEMENTS OF (PSEUDO) LINES (VOL 40,PG 189, 1991), Information processing letters, 51(1), 1994, pp. 53-56
Citations number
4
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
51
Issue
1
Year of publication
1994
Pages
53 - 56
Database
ISI
SICI code
0020-0190(1994)51:1<53:ODCCIA>2.0.ZU;2-#
Abstract
In the paper mentioned in the title [1] we have asserted that the maxi mum number of edges of m pairwise-disjoint x-monotone concave polygona l chains, contained in the union of n lines or pseudo lines, is THETA( m2/3n2/3+n). While the assertion is correct, the analysis of [1] was i ncomplete, and hence erroneous. In this note we complete the analysis and thus obtain a correct proof of the assertion.