Long monotone paths in line arrangements

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Long monotone paths in line arrangements

Full text

Pdf (199 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the nineteenth annual symposium on Computational geometry table of contents

San Diego, California, USA

SESSION: Partitions and arrangements table of contents

Pages: 124 - 128

Year of Publication: 2003

ISBN:1-58113-663-3

Authors

Jazsef Balogh	The Ohio State University
Oded Regev	Institute for Advanced Study, Princeton, NJ
Clifford Smyth	Carnegie-Mellon University, Pittsburgh, PA
William Steiger	Rutgers University
Mario Szegedy	Rutgers University

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/777792.777812 What is a DOI?

ABSTRACT

We show how to construct an arrangement of n lines having a monotone path of length O(n^{2-(d/vlog n)}), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	2	Jiří Matoušek, Lower bounds on the length of monotone paths in arrangements, Discrete & Computational Geometry, v.6 n.2, p.129-134, 1991 [doi>10.1007/BF02574679]
	3	Radovs Radoicić , Géza Tóth, Monotone paths in line arrangement, Proceedings of the seventeenth annual symposium on Computational geometry, p.312-314, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378711]