Constrained Delaunay Triangulation Using Delaunay Visibility View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Yi-Jun Yang , Hui Zhang , Jun-Hai Yong , Wei Zeng , Jean-Claude Paul , Jiaguang Sun

ABSTRACT

An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs. More... »

PAGES

682-691

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11919476_68

DOI

http://dx.doi.org/10.1007/11919476_68

DIMENSIONS

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


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 Computer Science and Tech., Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, Beijing, China", 
            "Department of Computer Science and Tech., Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Yi-Jun", 
        "id": "sg:person.010156164341.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010156164341.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Software, Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Hui", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Software, Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yong", 
        "givenName": "Jun-Hai", 
        "id": "sg:person.01071075202.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01071075202.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.424936.e", 
          "name": [
            "Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zeng", 
        "givenName": "Wei", 
        "id": "sg:person.0665065244.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0665065244.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Software, Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paul", 
        "givenName": "Jean-Claude", 
        "id": "sg:person.011611527417.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011611527417.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Tech., Tsinghua University, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, Beijing, China", 
            "Department of Computer Science and Tech., Tsinghua University, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sun", 
        "givenName": "Jiaguang", 
        "id": "sg:person.011411464635.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs.", 
    "editor": [
      {
        "familyName": "Bebis", 
        "givenName": "George", 
        "type": "Person"
      }, 
      {
        "familyName": "Boyle", 
        "givenName": "Richard", 
        "type": "Person"
      }, 
      {
        "familyName": "Parvin", 
        "givenName": "Bahram", 
        "type": "Person"
      }, 
      {
        "familyName": "Koracin", 
        "givenName": "Darko", 
        "type": "Person"
      }, 
      {
        "familyName": "Remagnino", 
        "givenName": "Paolo", 
        "type": "Person"
      }, 
      {
        "familyName": "Nefian", 
        "givenName": "Ara", 
        "type": "Person"
      }, 
      {
        "familyName": "Meenakshisundaram", 
        "givenName": "Gopi", 
        "type": "Person"
      }, 
      {
        "familyName": "Pascucci", 
        "givenName": "Valerio", 
        "type": "Person"
      }, 
      {
        "familyName": "Zara", 
        "givenName": "Jiri", 
        "type": "Person"
      }, 
      {
        "familyName": "Molineros", 
        "givenName": "Jose", 
        "type": "Person"
      }, 
      {
        "familyName": "Theisel", 
        "givenName": "Holger", 
        "type": "Person"
      }, 
      {
        "familyName": "Malzbender", 
        "givenName": "Tom", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11919476_68", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-48628-2", 
        "978-3-540-48631-2"
      ], 
      "name": "Advances in Visual Computing", 
      "type": "Book"
    }, 
    "keywords": [
      "CDT", 
      "time", 
      "number", 
      "straight-line graph", 
      "visibility", 
      "determination", 
      "conditions", 
      "method", 
      "cost", 
      "planar straight-line graph", 
      "existence", 
      "triangulation", 
      "time cost", 
      "complexity", 
      "edge", 
      "generator", 
      "algorithm", 
      "paper", 
      "grid method", 
      "Delaunay edges", 
      "computation of visibility", 
      "graph", 
      "sufficient conditions", 
      "Delaunay triangulation", 
      "visibility determination", 
      "number of edges", 
      "computation", 
      "mesh generator", 
      "linear time complexity", 
      "uniform grid method", 
      "time complexity", 
      "traditional visibility", 
      "Delaunay visibility", 
      "DT (CDT whose triangles are all Delaunay) existence"
    ], 
    "name": "Constrained Delaunay Triangulation Using Delaunay Visibility", 
    "pagination": "682-691", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049547381"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11919476_68"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11919476_68", 
      "https://app.dimensions.ai/details/publication/pub.1049547381"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_162.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11919476_68"
  }
]
 

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/11919476_68'

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/11919476_68'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11919476_68'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11919476_68'


 

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

188 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11919476_68 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N4d166173ac9f42029b7ef149d092d475
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description An algorithm for constructing constrained Delaunay triangulation (CDT) of a planar straight-line graph (PSLG) is presented. Although the uniform grid method can reduce the time cost of visibility determinations, the time needed to construct the CDT is still long. The algorithm proposed in this paper decreases the number of edges involved in the computation of visibility by replacing traditional visibility with Delaunay visibility. With Delaunay visibility introduced, all strongly Delaunay edges are excluded from the computation of visibility. Furthermore, a sufficient condition for DT (CDT whose triangles are all Delaunay) existence is presented to decrease the times of visibility determinations. The mesh generator is robust and exhibits a linear time complexity for randomly generated PSLGs.
7 schema:editor Ned3b0cd6831a4a20bfdfeeae787267fe
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N1f23a33262da4f4daee07638a9027661
12 schema:keywords CDT
13 DT (CDT whose triangles are all Delaunay) existence
14 Delaunay edges
15 Delaunay triangulation
16 Delaunay visibility
17 algorithm
18 complexity
19 computation
20 computation of visibility
21 conditions
22 cost
23 determination
24 edge
25 existence
26 generator
27 graph
28 grid method
29 linear time complexity
30 mesh generator
31 method
32 number
33 number of edges
34 paper
35 planar straight-line graph
36 straight-line graph
37 sufficient conditions
38 time
39 time complexity
40 time cost
41 traditional visibility
42 triangulation
43 uniform grid method
44 visibility
45 visibility determination
46 schema:name Constrained Delaunay Triangulation Using Delaunay Visibility
47 schema:pagination 682-691
48 schema:productId N0211fdb897db4300820a46444c69dd35
49 N8f7d97b4281b4223acc3dd5d77d05352
50 schema:publisher N6f33f015fe4d4159b99912e3afce5f02
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049547381
52 https://doi.org/10.1007/11919476_68
53 schema:sdDatePublished 2022-01-01T19:09
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N4739d10f69f7429eb8cc99fe3a82425a
56 schema:url https://doi.org/10.1007/11919476_68
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N018fc36ea37846a2b223f90b71d836c6 schema:familyName Pascucci
61 schema:givenName Valerio
62 rdf:type schema:Person
63 N01dd00d4ea014c819b82d6a922620294 schema:familyName Parvin
64 schema:givenName Bahram
65 rdf:type schema:Person
66 N0211fdb897db4300820a46444c69dd35 schema:name dimensions_id
67 schema:value pub.1049547381
68 rdf:type schema:PropertyValue
69 N05f91a1cac054a4a950bdb3096332fe6 rdf:first sg:person.0665065244.67
70 rdf:rest N4bfd7778bf624349a1e1260b0f5c7495
71 N15cf8d7539d343fc8e843c373675c113 rdf:first N018fc36ea37846a2b223f90b71d836c6
72 rdf:rest N97db43f6ed5e4c2ea8af1572c153cc8c
73 N15dc354ed0344452bac710200f8acb5d rdf:first N5293bdc5ff0d45d78ab866081ec578eb
74 rdf:rest N1eadfb68eeae49e7a66aaf92d80f4f80
75 N1eadfb68eeae49e7a66aaf92d80f4f80 rdf:first N39a79fbc43874cfb9f54f7709b8bd954
76 rdf:rest rdf:nil
77 N1f23a33262da4f4daee07638a9027661 schema:isbn 978-3-540-48628-2
78 978-3-540-48631-2
79 schema:name Advances in Visual Computing
80 rdf:type schema:Book
81 N265855c8bc3a44b9b36622c1176b8f02 schema:familyName Koracin
82 schema:givenName Darko
83 rdf:type schema:Person
84 N31c82d66d6e5450d89327aca45b0bb96 schema:familyName Remagnino
85 schema:givenName Paolo
86 rdf:type schema:Person
87 N39a79fbc43874cfb9f54f7709b8bd954 schema:familyName Malzbender
88 schema:givenName Tom
89 rdf:type schema:Person
90 N3dad212121d54991a9a59df18a2197e9 rdf:first N265855c8bc3a44b9b36622c1176b8f02
91 rdf:rest Na1f1137ab6b94208a74965fbe6d5daf0
92 N3e56e3edb38747269acb85e2a78b465c schema:affiliation grid-institutes:grid.12527.33
93 schema:familyName Zhang
94 schema:givenName Hui
95 rdf:type schema:Person
96 N4739d10f69f7429eb8cc99fe3a82425a schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 N4bfd7778bf624349a1e1260b0f5c7495 rdf:first sg:person.011611527417.75
99 rdf:rest Nb304dae30d004525b6a1e0f9162d73f8
100 N4d166173ac9f42029b7ef149d092d475 rdf:first sg:person.010156164341.42
101 rdf:rest Nfdecc6d49df04a21b6359b90dbbaeac3
102 N4d4f0ab7f4354d05ab57b1a958e1c57b schema:familyName Meenakshisundaram
103 schema:givenName Gopi
104 rdf:type schema:Person
105 N4d7ee79644c24048ac5a12bf95ddfab2 schema:familyName Bebis
106 schema:givenName George
107 rdf:type schema:Person
108 N505284bff44f4012a42c799845f13be8 rdf:first Nfb3ea9aeaf374d5aba59383c25360ddc
109 rdf:rest Nf8dc5f51b3b343e4973f8cf666815c35
110 N5293bdc5ff0d45d78ab866081ec578eb schema:familyName Theisel
111 schema:givenName Holger
112 rdf:type schema:Person
113 N5cf7f4c764de469bbac41f29e14c957a rdf:first N6c9b2aed3c754c6181b12e6ee74ecc96
114 rdf:rest N15dc354ed0344452bac710200f8acb5d
115 N5dc5f1c1b6934a2b9e3f584510be5f15 rdf:first sg:person.01071075202.49
116 rdf:rest N05f91a1cac054a4a950bdb3096332fe6
117 N6c9b2aed3c754c6181b12e6ee74ecc96 schema:familyName Molineros
118 schema:givenName Jose
119 rdf:type schema:Person
120 N6f33f015fe4d4159b99912e3afce5f02 schema:name Springer Nature
121 rdf:type schema:Organisation
122 N8f7d97b4281b4223acc3dd5d77d05352 schema:name doi
123 schema:value 10.1007/11919476_68
124 rdf:type schema:PropertyValue
125 N97db43f6ed5e4c2ea8af1572c153cc8c rdf:first Ndf529b755e5440aeb1dfce454fefbafc
126 rdf:rest N5cf7f4c764de469bbac41f29e14c957a
127 Na1f1137ab6b94208a74965fbe6d5daf0 rdf:first N31c82d66d6e5450d89327aca45b0bb96
128 rdf:rest N505284bff44f4012a42c799845f13be8
129 Nb304dae30d004525b6a1e0f9162d73f8 rdf:first sg:person.011411464635.59
130 rdf:rest rdf:nil
131 Nba5795cd1af243edb44bed89df78cb1b rdf:first N01dd00d4ea014c819b82d6a922620294
132 rdf:rest N3dad212121d54991a9a59df18a2197e9
133 Nd92dcc4606c94d9e862c453fe370b6d3 rdf:first Nf714872dbe4b46a99ca82f7666d351fd
134 rdf:rest Nba5795cd1af243edb44bed89df78cb1b
135 Ndf529b755e5440aeb1dfce454fefbafc schema:familyName Zara
136 schema:givenName Jiri
137 rdf:type schema:Person
138 Ned3b0cd6831a4a20bfdfeeae787267fe rdf:first N4d7ee79644c24048ac5a12bf95ddfab2
139 rdf:rest Nd92dcc4606c94d9e862c453fe370b6d3
140 Nf714872dbe4b46a99ca82f7666d351fd schema:familyName Boyle
141 schema:givenName Richard
142 rdf:type schema:Person
143 Nf8dc5f51b3b343e4973f8cf666815c35 rdf:first N4d4f0ab7f4354d05ab57b1a958e1c57b
144 rdf:rest N15cf8d7539d343fc8e843c373675c113
145 Nfb3ea9aeaf374d5aba59383c25360ddc schema:familyName Nefian
146 schema:givenName Ara
147 rdf:type schema:Person
148 Nfdecc6d49df04a21b6359b90dbbaeac3 rdf:first N3e56e3edb38747269acb85e2a78b465c
149 rdf:rest N5dc5f1c1b6934a2b9e3f584510be5f15
150 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
151 schema:name Information and Computing Sciences
152 rdf:type schema:DefinedTerm
153 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
154 schema:name Computation Theory and Mathematics
155 rdf:type schema:DefinedTerm
156 sg:person.010156164341.42 schema:affiliation grid-institutes:grid.12527.33
157 schema:familyName Yang
158 schema:givenName Yi-Jun
159 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010156164341.42
160 rdf:type schema:Person
161 sg:person.01071075202.49 schema:affiliation grid-institutes:grid.12527.33
162 schema:familyName Yong
163 schema:givenName Jun-Hai
164 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01071075202.49
165 rdf:type schema:Person
166 sg:person.011411464635.59 schema:affiliation grid-institutes:grid.12527.33
167 schema:familyName Sun
168 schema:givenName Jiaguang
169 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011411464635.59
170 rdf:type schema:Person
171 sg:person.011611527417.75 schema:affiliation grid-institutes:grid.12527.33
172 schema:familyName Paul
173 schema:givenName Jean-Claude
174 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011611527417.75
175 rdf:type schema:Person
176 sg:person.0665065244.67 schema:affiliation grid-institutes:grid.424936.e
177 schema:familyName Zeng
178 schema:givenName Wei
179 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0665065244.67
180 rdf:type schema:Person
181 grid-institutes:grid.12527.33 schema:alternateName Department of Computer Science and Tech., Tsinghua University, Beijing, China
182 School of Software, Tsinghua University, Beijing, China
183 schema:name Department of Computer Science and Tech., Tsinghua University, Beijing, China
184 School of Software, Tsinghua University, Beijing, China
185 rdf:type schema:Organization
186 grid-institutes:grid.424936.e schema:alternateName Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
187 schema:name Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China
188 rdf:type schema:Organization
 




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


...