Hierarchical Topological Inference on Planar Disc Maps View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2000-07-21

AUTHORS

Zhi-Zhong Chen , Xin He

ABSTRACT

Given a set V and three relations ⋈d, ⋈m and ⋈i, we wish to ask whether it is possible to draw the elements v ∈ V each as a closed disc homeomorph in the plane in such a way that (1) and are disjoint for every (v,w) ∈⋈d, (2) and have disjoint interiors but share a point of their boundaries for every (v,w) ∈⋈m, and (3) includes as a sub-region for every (v,w) ∈⋈i. 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. More... »

PAGES

115-125

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44968-x_12

DOI

http://dx.doi.org/10.1007/3-540-44968-x_12

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1044596440


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Comput. Sci. and Engin., State Univ. of New York at Buffalo, 14260, Buffalo, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Dept. of Comput. Sci. and Engin., State Univ. of New York at Buffalo, 14260, Buffalo, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-07-21", 
    "datePublishedReg": "2000-07-21", 
    "description": "Given a set V and three relations \u22c8d, \u22c8m and \u22c8i, we wish to ask whether it is possible to draw the elements v \u2208 V each as a closed disc homeomorph in the plane in such a way that (1) and are disjoint for every (v,w) \u2208\u22c8d, (2) and have disjoint interiors but share a point of their boundaries for every (v,w) \u2208\u22c8m, and (3) includes as a sub-region for every (v,w) \u2208\u22c8i. 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.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Eades", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Estivill-Castro", 
        "givenName": "Vladimir", 
        "type": "Person"
      }, 
      {
        "familyName": "Lin", 
        "givenName": "Xuemin", 
        "type": "Person"
      }, 
      {
        "familyName": "Sharma", 
        "givenName": "Arun", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44968-x_12", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67787-1", 
        "978-3-540-44968-3"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "information systems", 
      "geographic information system", 
      "linear time", 
      "topological inference", 
      "NP", 
      "disk map", 
      "nontrivial special case", 
      "disjoint", 
      "special case", 
      "disjoint interiors", 
      "inference", 
      "maps", 
      "system", 
      "way", 
      "point", 
      "time", 
      "boundaries", 
      "plane", 
      "cases", 
      "relation", 
      "homeomorphs", 
      "study", 
      "interior", 
      "elements V", 
      "problem", 
      "paper", 
      "closed disc homeomorph", 
      "disc homeomorph", 
      "Hierarchical Topological Inference", 
      "Planar Disc Maps"
    ], 
    "name": "Hierarchical Topological Inference on Planar Disc Maps", 
    "pagination": "115-125", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044596440"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44968-x_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44968-x_12", 
      "https://app.dimensions.ai/details/publication/pub.1044596440"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_288.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44968-x_12"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-44968-x_12'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-44968-x_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44968-x_12'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-44968-x_12'


 

This table displays all metadata directly associated to this object as RDF triples.

120 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44968-x_12 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N0af9e0eeeb3240ed9c574e607afad639
4 schema:datePublished 2000-07-21
5 schema:datePublishedReg 2000-07-21
6 schema:description Given a set V and three relations ⋈d, ⋈m and ⋈i, we wish to ask whether it is possible to draw the elements v ∈ V each as a closed disc homeomorph in the plane in such a way that (1) and are disjoint for every (v,w) ∈⋈d, (2) and have disjoint interiors but share a point of their boundaries for every (v,w) ∈⋈m, and (3) includes as a sub-region for every (v,w) ∈⋈i. 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.
7 schema:editor N1254c04cba3c453ebd6cd9e2f3cd7d57
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N6e3afcf896f94ff9b293d373ab0a4240
12 schema:keywords Hierarchical Topological Inference
13 NP
14 Planar Disc Maps
15 boundaries
16 cases
17 closed disc homeomorph
18 disc homeomorph
19 disjoint
20 disjoint interiors
21 disk map
22 elements V
23 geographic information system
24 homeomorphs
25 inference
26 information systems
27 interior
28 linear time
29 maps
30 nontrivial special case
31 paper
32 plane
33 point
34 problem
35 relation
36 special case
37 study
38 system
39 time
40 topological inference
41 way
42 schema:name Hierarchical Topological Inference on Planar Disc Maps
43 schema:pagination 115-125
44 schema:productId N20eaea2d8bbd42a3b7c4ac66f534a5e0
45 N27bdeabe6af64111a586876ff515a63e
46 schema:publisher N027ac03671d9448d80d00e61429953d0
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044596440
48 https://doi.org/10.1007/3-540-44968-x_12
49 schema:sdDatePublished 2021-11-01T18:54
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N86dd926a3eba44bbabca31fd5ebbdd99
52 schema:url https://doi.org/10.1007/3-540-44968-x_12
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N027ac03671d9448d80d00e61429953d0 schema:name Springer Nature
57 rdf:type schema:Organisation
58 N09bb1bcd47ad4ec5acf476b8148e785c rdf:first sg:person.011352641523.42
59 rdf:rest rdf:nil
60 N0af9e0eeeb3240ed9c574e607afad639 rdf:first sg:person.015654265661.98
61 rdf:rest N09bb1bcd47ad4ec5acf476b8148e785c
62 N0d3c60bb3396433cb157af290f27ea44 rdf:first N35b30de13fea470dadcd76b67fafa1e6
63 rdf:rest Nc5aa12717b0941c9a09ff333bb7838e3
64 N1254c04cba3c453ebd6cd9e2f3cd7d57 rdf:first N882c87e67159402ca318edb3521b4d20
65 rdf:rest Nb976b9279d314ceead25413f1769af11
66 N1c12caa0acc24c85a9a3f25136aa9be9 schema:familyName Lin
67 schema:givenName Xuemin
68 rdf:type schema:Person
69 N20eaea2d8bbd42a3b7c4ac66f534a5e0 schema:name dimensions_id
70 schema:value pub.1044596440
71 rdf:type schema:PropertyValue
72 N27bdeabe6af64111a586876ff515a63e schema:name doi
73 schema:value 10.1007/3-540-44968-x_12
74 rdf:type schema:PropertyValue
75 N35b30de13fea470dadcd76b67fafa1e6 schema:familyName Estivill-Castro
76 schema:givenName Vladimir
77 rdf:type schema:Person
78 N4f4d980fe3354d91b5e9d1de2cc98145 schema:familyName Eades
79 schema:givenName Peter
80 rdf:type schema:Person
81 N6e3afcf896f94ff9b293d373ab0a4240 schema:isbn 978-3-540-44968-3
82 978-3-540-67787-1
83 schema:name Computing and Combinatorics
84 rdf:type schema:Book
85 N86dd926a3eba44bbabca31fd5ebbdd99 schema:name Springer Nature - SN SciGraph project
86 rdf:type schema:Organization
87 N882c87e67159402ca318edb3521b4d20 schema:familyName Du
88 schema:givenName Ding-Zhu
89 rdf:type schema:Person
90 Na3e393f3074841c799b469a80c434dec rdf:first Nc5f2b879172d4012b73f9a33ed36cbc9
91 rdf:rest rdf:nil
92 Nb976b9279d314ceead25413f1769af11 rdf:first N4f4d980fe3354d91b5e9d1de2cc98145
93 rdf:rest N0d3c60bb3396433cb157af290f27ea44
94 Nc5aa12717b0941c9a09ff333bb7838e3 rdf:first N1c12caa0acc24c85a9a3f25136aa9be9
95 rdf:rest Na3e393f3074841c799b469a80c434dec
96 Nc5f2b879172d4012b73f9a33ed36cbc9 schema:familyName Sharma
97 schema:givenName Arun
98 rdf:type schema:Person
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
103 schema:name Computation Theory and Mathematics
104 rdf:type schema:DefinedTerm
105 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
106 schema:familyName He
107 schema:givenName Xin
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
109 rdf:type schema:Person
110 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
111 schema:familyName Chen
112 schema:givenName Zhi-Zhong
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
114 rdf:type schema:Person
115 grid-institutes:grid.273335.3 schema:alternateName Dept. of Comput. Sci. and Engin., State Univ. of New York at Buffalo, 14260, Buffalo, NY, USA
116 schema:name Dept. of Comput. Sci. and Engin., State Univ. of New York at Buffalo, 14260, Buffalo, NY, USA
117 rdf:type schema:Organization
118 grid-institutes:grid.412773.4 schema:alternateName Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
119 schema:name Department of Mathematical Sciences, Tokyo Denki University, Hatoyama, 350-0394, Saitama, Japan
120 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...