Long monotone paths in line arrangements

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

Long monotone paths in line arrangements

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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)
Title of host publication	Proceedings of the Annual Symposium on Computational Geometry
Pages	124-128
Number of pages	5
State	Published - 2003
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

Software
Geometry and Topology
Safety, Risk, Reliability and Quality
Chemical Health and Safety

Cite this

@inproceedings{8752433bdffc42d1bb32cb3de319068c,

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",

language = "English (US)",

pages = "124--128",

booktitle = "Proceedings of the Annual Symposium on Computational Geometry",

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

}

TY - GEN

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

M3 - Conference contribution

AN - SCOPUS:0038714823

SP - 124

EP - 128

BT - Proceedings of the Annual Symposium on Computational Geometry

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

Other files and links

Fingerprint

Cite this