Long monotone paths in line arrangements

József Balogh; Oded Regev; Clifford Smyth; William Steiger; Mario Szegedy

doi:10.1007/s00454-004-1119-1

Long monotone paths in line arrangements

József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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

Original language	English (US)
Pages (from-to)	167-176
Number of pages	10
Journal	Discrete and Computational Geometry
Volume	32
Issue number	2
DOIs	https://doi.org/10.1007/s00454-004-1119-1
State	Published - Sep 2004

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-004-1119-1

Cite this

@article{f0dca027cd134405948ff69e05dc6b9b,

title = "Long monotone paths in line arrangements",

abstract = "We show how to construct an arrangement of n lines having a monotone path of length Ω(n2-(d/√logn), where d > 0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.",

author = "J{\'o}zsef Balogh and Oded Regev and Clifford Smyth and William Steiger and Mario Szegedy",

year = "2004",

month = sep,

doi = "10.1007/s00454-004-1119-1",

language = "English (US)",

volume = "32",

pages = "167--176",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - Long monotone paths in line arrangements

AU - Balogh, József

AU - Regev, Oded

AU - Smyth, Clifford

AU - Steiger, William

AU - Szegedy, Mario

PY - 2004/9

Y1 - 2004/9

N2 - We show how to construct an arrangement of n lines having a monotone path of length Ω(n2-(d/√logn), where d > 0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

AB - We show how to construct an arrangement of n lines having a monotone path of length Ω(n2-(d/√logn), where d > 0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

UR - http://www.scopus.com/inward/record.url?scp=4344580535&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=4344580535&partnerID=8YFLogxK

U2 - 10.1007/s00454-004-1119-1

DO - 10.1007/s00454-004-1119-1

M3 - Article

AN - SCOPUS:4344580535

SN - 0179-5376

VL - 32

SP - 167

EP - 176

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 2

ER -

Long monotone paths in line arrangements

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this