Long monotone paths in line arrangements

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

doi:10.1145/777792.777812

Long monotone paths in line arrangements

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

Research output: Contribution to conference › Paper › peer-review

Abstract

The method to construct an arrangement of n lines having a monotone path was presented. It was observed that k parallel horizontal lines and k parallel vertical lines uses n lines and has a length n=2k. It was found that a path is monotone in direction (a,b) if its sequence of vertices is monotone when projected orthogonally along the line with equation ay-bx=0.

Original language	English (US)
Pages	124-128
Number of pages	5
DOIs	https://doi.org/10.1145/777792.777812
State	Published - 2003
Externally published	Yes
Event	Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: Jun 8 2003 → Jun 10 2003

Other

Other	Nineteenth Annual Symposium on Computational Geometry
Country/Territory	United States
City	san Diego, CA
Period	6/8/03 → 6/10/03

Keywords

Discrete Line Arrangements
Monotone Paths

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Online availability

10.1145/777792.777812

Library availability

Discover UIUC Full Text

Cite this

@conference{848f85c034ee4bf58d497c297570a143,

title = "Long monotone paths in line arrangements",

abstract = "The method to construct an arrangement of n lines having a monotone path was presented. It was observed that k parallel horizontal lines and k parallel vertical lines uses n lines and has a length n=2k. It was found that a path is monotone in direction (a,b) if its sequence of vertices is monotone when projected orthogonally along the line with equation ay-bx=0.",

keywords = "Discrete Line Arrangements, Monotone Paths",

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

year = "2003",

doi = "10.1145/777792.777812",

language = "English (US)",

pages = "124--128",

note = "Nineteenth Annual Symposium on Computational Geometry ; Conference date: 08-06-2003 Through 10-06-2003",

}

TY - CONF

T1 - Long monotone paths in line arrangements

AU - Balogh, József

AU - Regev, Oded

AU - Smyth, Clifford

AU - Steiger, William

AU - Szegedy, Mario

PY - 2003

Y1 - 2003

N2 - The method to construct an arrangement of n lines having a monotone path was presented. It was observed that k parallel horizontal lines and k parallel vertical lines uses n lines and has a length n=2k. It was found that a path is monotone in direction (a,b) if its sequence of vertices is monotone when projected orthogonally along the line with equation ay-bx=0.

AB - The method to construct an arrangement of n lines having a monotone path was presented. It was observed that k parallel horizontal lines and k parallel vertical lines uses n lines and has a length n=2k. It was found that a path is monotone in direction (a,b) if its sequence of vertices is monotone when projected orthogonally along the line with equation ay-bx=0.

KW - Discrete Line Arrangements

KW - Monotone Paths

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

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

U2 - 10.1145/777792.777812

DO - 10.1145/777792.777812

M3 - Paper

AN - SCOPUS:0038714823

SP - 124

EP - 128

T2 - Nineteenth Annual Symposium on Computational Geometry

Y2 - 8 June 2003 through 10 June 2003

ER -

Long monotone paths in line arrangements

Abstract

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this