Hierarchical topological inference on planar disc maps

Zhi Zhong Chen; Xin He

doi:10.1007/3-540-44968-x_12

Hierarchical topological inference on planar disc maps

Zhi Zhong Chen
, Xin He

Department of Computer Science and Engineering

Tokyo Denki University

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

1 Scopus citations

Abstract

Given a set V and three relations (formula presented) and (formula presented) we wish to ask whether it is possible to draw the elements v {small element of} V each as a closed disc homeomorph D_v in the plane in such a way that (1) D_v and D_w are disjoint for every (v,w) (formula presented), (2) Dv and Dw have disjoint interiors but share a point of their boundaries for every (v,w) (formula presented), and (3) D_v includes D_w as a sub-region for every (formula presented). This problem arises from the study in geographic information systems. The problem is in NP but not known to be NP-hard or polynomial-time solvable. This paper shows that a nontrivial special case of the problem can be solved in almost linear time.

Original language	English
Title of host publication	Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings
Editors	Ding-Zhu Du, Peter Eades, Vladimir Estivill-Castro, Xuemin Lin, Arun Sharma
Publisher	Springer Verlag
Pages	115-125
Number of pages	11
ISBN (Print)	3540677879, 9783540677871
DOIs	https://doi.org/10.1007/3-540-44968-x_12
State	Published - 2000
Event	6th Annual International Conference on Computing and Combinatorics, COCOON 2000 - Sydney, Australia Duration: Jul 26 2000 → Jul 28 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1858
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th Annual International Conference on Computing and Combinatorics, COCOON 2000
Country/Territory	Australia
City	Sydney
Period	07/26/00 → 07/28/00

Access to Document

10.1007/3-540-44968-x_12

Cite this

Chen, Z. Z., & He, X. (2000). Hierarchical topological inference on planar disc maps. In D.-Z. Du, P. Eades, V. Estivill-Castro, X. Lin, & A. Sharma (Eds.), Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings (pp. 115-125). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1858). Springer Verlag. https://doi.org/10.1007/3-540-44968-x_12

Chen, Zhi Zhong ; He, Xin. / Hierarchical topological inference on planar disc maps. Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings. editor / Ding-Zhu Du ; Peter Eades ; Vladimir Estivill-Castro ; Xuemin Lin ; Arun Sharma. Springer Verlag, 2000. pp. 115-125 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{37cd0dbb1081480bb5a1a4950adeef99,

title = "Hierarchical topological inference on planar disc maps",

abstract = "Given a set V and three relations (formula presented) and (formula presented) we wish to ask whether it is possible to draw the elements v \{small element of\} V each as a closed disc homeomorph Dv in the plane in such a way that (1) Dv and Dw are disjoint for every (v,w) (formula presented), (2) Dv and Dw have disjoint interiors but share a point of their boundaries for every (v,w) (formula presented), and (3) Dv includes Dw as a sub-region for every (formula presented). This problem arises from the study in geographic information systems. The problem is in NP but not known to be NP-hard or polynomial-time solvable. This paper shows that a nontrivial special case of the problem can be solved in almost linear time.",

author = "Chen, \{Zhi Zhong\} and Xin He",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 6th Annual International Conference on Computing and Combinatorics, COCOON 2000 ; Conference date: 26-07-2000 Through 28-07-2000",

year = "2000",

doi = "10.1007/3-540-44968-x\_12",

language = "English",

isbn = "3540677879",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "115--125",

editor = "Ding-Zhu Du and Peter Eades and Vladimir Estivill-Castro and Xuemin Lin and Arun Sharma",

booktitle = "Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings",

address = "Germany",

}

Chen, ZZ & He, X 2000, Hierarchical topological inference on planar disc maps. in D-Z Du, P Eades, V Estivill-Castro, X Lin & A Sharma (eds), Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1858, Springer Verlag, pp. 115-125, 6th Annual International Conference on Computing and Combinatorics, COCOON 2000, Sydney, Australia, 07/26/00. https://doi.org/10.1007/3-540-44968-x_12

Hierarchical topological inference on planar disc maps. / Chen, Zhi Zhong; He, Xin.
Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings. ed. / Ding-Zhu Du; Peter Eades; Vladimir Estivill-Castro; Xuemin Lin; Arun Sharma. Springer Verlag, 2000. p. 115-125 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1858).

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

TY - GEN

T1 - Hierarchical topological inference on planar disc maps

AU - Chen, Zhi Zhong

AU - He, Xin

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000.

PY - 2000

Y1 - 2000

N2 - Given a set V and three relations (formula presented) and (formula presented) we wish to ask whether it is possible to draw the elements v {small element of} V each as a closed disc homeomorph Dv in the plane in such a way that (1) Dv and Dw are disjoint for every (v,w) (formula presented), (2) Dv and Dw have disjoint interiors but share a point of their boundaries for every (v,w) (formula presented), and (3) Dv includes Dw as a sub-region for every (formula presented). This problem arises from the study in geographic information systems. The problem is in NP but not known to be NP-hard or polynomial-time solvable. This paper shows that a nontrivial special case of the problem can be solved in almost linear time.

AB - Given a set V and three relations (formula presented) and (formula presented) we wish to ask whether it is possible to draw the elements v {small element of} V each as a closed disc homeomorph Dv in the plane in such a way that (1) Dv and Dw are disjoint for every (v,w) (formula presented), (2) Dv and Dw have disjoint interiors but share a point of their boundaries for every (v,w) (formula presented), and (3) Dv includes Dw as a sub-region for every (formula presented). This problem arises from the study in geographic information systems. The problem is in NP but not known to be NP-hard or polynomial-time solvable. This paper shows that a nontrivial special case of the problem can be solved in almost linear time.

UR - https://www.scopus.com/pages/publications/84956983398

U2 - 10.1007/3-540-44968-x_12

DO - 10.1007/3-540-44968-x_12

M3 - Conference contribution

AN - SCOPUS:84956983398

SN - 3540677879

SN - 9783540677871

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 125

BT - Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings

A2 - Du, Ding-Zhu

A2 - Eades, Peter

A2 - Estivill-Castro, Vladimir

A2 - Lin, Xuemin

A2 - Sharma, Arun

PB - Springer Verlag

T2 - 6th Annual International Conference on Computing and Combinatorics, COCOON 2000

Y2 - 26 July 2000 through 28 July 2000

ER -

Chen ZZ, He X. Hierarchical topological inference on planar disc maps. In Du DZ, Eades P, Estivill-Castro V, Lin X, Sharma A, editors, Computing and Combinatorics - 6th Annual International Conference, COCOON 2000, Proceedings. Springer Verlag. 2000. p. 115-125. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44968-x_12

Hierarchical topological inference on planar disc maps

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this