Placing segments on parallel arcs

Yen Kaow Ng; Wenlong Jia; Shuai Cheng Li

doi:10.1007/978-3-319-94667-2_25

Placing segments on parallel arcs

Yen Kaow Ng, Wenlong Jia, Shuai Cheng Li

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

In this paper we consider the problem of arranging segments on parallel arcs drawn within a circular sector, to provide foundational work for the visualization of genomic regions in the study of pathogenic integration. The arcs as well as the start and end angles for each segment are pre-defined; our problem is to place each segment on an arc without having them overlap. There are no segments that span multiple arcs. For visualization purpose, the segments are to be easily distinguishable. To achieve that we consider various criteria that in a sense, place segments as far as possible from each other—for instance, maximizing the sum of inter-center distances between nearest segments. We show complexity results for some of the resultant problems, while providing approximation or heuristic solutions for others. Our algorithms have been implemented in JavaScript and made available at https://github.com/kalngyk/segmentplacer.

Original language	English
Title of host publication	Combinatorial Algorithms
Subtitle of host publication	29th International Workshop, IWOCA 2018, Proceedings
Editors	Costas Iliopoulos, Hon Wai Leong, Wing-Kin Sung
Publisher	Springer International Publishing
Pages	298-310
ISBN (Electronic)	9783319946672
ISBN (Print)	9783319946665
DOIs	https://doi.org/10.1007/978-3-319-94667-2_25
Publication status	Published - 2018
Event	29th International Workshop on Combinatorial Algorithms, IWOCA 2018 - Singapore, Singapore Duration: 16 Jul 2018 → 19 Jul 2018

Publication series

Name	Lecture Notes in Computer Science
Volume	10979
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Workshop on Combinatorial Algorithms, IWOCA 2018
Country/Territory	Singapore
City	Singapore
Period	16/07/18 → 19/07/18

Research Keywords

Approximation algorithm
Segment placement
Visualization

Access Output

10.1007/978-3-319-94667-2_25

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{4f0799d3cf0843038e2dbc89008e1379,

title = "Placing segments on parallel arcs",

abstract = "In this paper we consider the problem of arranging segments on parallel arcs drawn within a circular sector, to provide foundational work for the visualization of genomic regions in the study of pathogenic integration. The arcs as well as the start and end angles for each segment are pre-defined; our problem is to place each segment on an arc without having them overlap. There are no segments that span multiple arcs. For visualization purpose, the segments are to be easily distinguishable. To achieve that we consider various criteria that in a sense, place segments as far as possible from each other—for instance, maximizing the sum of inter-center distances between nearest segments. We show complexity results for some of the resultant problems, while providing approximation or heuristic solutions for others. Our algorithms have been implemented in JavaScript and made available at https://github.com/kalngyk/segmentplacer.",

keywords = "Approximation algorithm, Segment placement, Visualization",

author = "Ng, {Yen Kaow} and Wenlong Jia and Li, {Shuai Cheng}",

year = "2018",

doi = "10.1007/978-3-319-94667-2_25",

language = "English",

isbn = "9783319946665",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing ",

pages = "298--310",

editor = "Costas Iliopoulos and Leong, {Hon Wai} and Wing-Kin Sung",

booktitle = "Combinatorial Algorithms",

address = "Switzerland",

note = "29th International Workshop on Combinatorial Algorithms, IWOCA 2018 ; Conference date: 16-07-2018 Through 19-07-2018",

}

Ng, YK, Jia, W & Li, SC 2018, Placing segments on parallel arcs. in C Iliopoulos, HW Leong & W-K Sung (eds), Combinatorial Algorithms: 29th International Workshop, IWOCA 2018, Proceedings. Lecture Notes in Computer Science, vol. 10979, Springer International Publishing , pp. 298-310, 29th International Workshop on Combinatorial Algorithms, IWOCA 2018, Singapore, Singapore, 16/07/18. https://doi.org/10.1007/978-3-319-94667-2_25

Placing segments on parallel arcs. / Ng, Yen Kaow; Jia, Wenlong ; Li, Shuai Cheng.
Combinatorial Algorithms: 29th International Workshop, IWOCA 2018, Proceedings. ed. / Costas Iliopoulos; Hon Wai Leong; Wing-Kin Sung. Springer International Publishing , 2018. p. 298-310 (Lecture Notes in Computer Science; Vol. 10979).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Placing segments on parallel arcs

AU - Ng, Yen Kaow

AU - Jia, Wenlong

AU - Li, Shuai Cheng

PY - 2018

Y1 - 2018

N2 - In this paper we consider the problem of arranging segments on parallel arcs drawn within a circular sector, to provide foundational work for the visualization of genomic regions in the study of pathogenic integration. The arcs as well as the start and end angles for each segment are pre-defined; our problem is to place each segment on an arc without having them overlap. There are no segments that span multiple arcs. For visualization purpose, the segments are to be easily distinguishable. To achieve that we consider various criteria that in a sense, place segments as far as possible from each other—for instance, maximizing the sum of inter-center distances between nearest segments. We show complexity results for some of the resultant problems, while providing approximation or heuristic solutions for others. Our algorithms have been implemented in JavaScript and made available at https://github.com/kalngyk/segmentplacer.

AB - In this paper we consider the problem of arranging segments on parallel arcs drawn within a circular sector, to provide foundational work for the visualization of genomic regions in the study of pathogenic integration. The arcs as well as the start and end angles for each segment are pre-defined; our problem is to place each segment on an arc without having them overlap. There are no segments that span multiple arcs. For visualization purpose, the segments are to be easily distinguishable. To achieve that we consider various criteria that in a sense, place segments as far as possible from each other—for instance, maximizing the sum of inter-center distances between nearest segments. We show complexity results for some of the resultant problems, while providing approximation or heuristic solutions for others. Our algorithms have been implemented in JavaScript and made available at https://github.com/kalngyk/segmentplacer.

KW - Approximation algorithm

KW - Segment placement

KW - Visualization

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

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85049909077&origin=recordpage

U2 - 10.1007/978-3-319-94667-2_25

DO - 10.1007/978-3-319-94667-2_25

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319946665

T3 - Lecture Notes in Computer Science

SP - 298

EP - 310

BT - Combinatorial Algorithms

A2 - Iliopoulos, Costas

A2 - Leong, Hon Wai

A2 - Sung, Wing-Kin

PB - Springer International Publishing

T2 - 29th International Workshop on Combinatorial Algorithms, IWOCA 2018

Y2 - 16 July 2018 through 19 July 2018

ER -

Placing segments on parallel arcs

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this