Non-Simplicial Delaunay Meshing via Approximation by Radical Partitions View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-08

AUTHORS

V. A. Garanzha, L. N. Kudryavtseva, L. Kamenski

ABSTRACT

We consider the construction of a polyhedral Delaunay partition as a limit of the sequence of power diagrams (in Russian traditionally called radical partitions), while the dual Voronoi diagram is obtained as a limit of the sequence of weighted Delaunay partitions. Using a lifting analogy, this problem is reduced to the construction of a pair of dual convex polyhedra, inscribed and superscribed around a circular paraboloid, as a limit of the sequence of pairs of general dual convex polyhedra. The sequence of primal polyhedra should converge to the superscribed polyhedron, while the sequence of dual polyhedra converges to the inscribed polyhedron. For building sequences of dual polyhedra we are mostly interested in the case when the vertices of primal polyhedra can move or merge together. This means that no new faces are allowed for dual polyhedra. These rules essentially define the transformation of the set of initial spheres defining a power diagram into the set of Delaunay spheres using sphere movement, radius variation, and sphere elimination as admissible operations. Although a rigorous foundation (existence theorems) for this problem is still unavailable, we suggest a functional measuring the deviation of the convex polyhedron from the one inscribed into the paraboloid. This functional is the discrete Dirichlet functional for the power function (power of a point with respect to a ball) which is a linear interpolant of the vertical distance of the dual vertices from the paraboloid. The absolute minimizer of this functional is attained on the constant power field, meaning that the inscribed polyhedron can be obtained using a simple translation. This formulation of the Dirichlet functional for the dual surface is not quadratic since the unknowns are the vertices of the primal polyhedron. Hence, the transformation of the set of spheres into Delaunay spheres is not unique. In this work, we concentrate on the experimental confirmation of the viability of suggested approach and put aside mesh quality problems. The zero value of the gradient of the proposed functional defines a manifold describing the evolution of Delaunay spheres. Hence, Delaunay–Voronoi meshes can be optimized using this manifold as a constraint. Numerical examples illustrate polygonal Delaunay meshing in planar domains. More... »

PAGES

1203-1216

Identifiers

URI

http://scigraph.springernature.com/pub.10.1134/s096554252208005x

DOI

http://dx.doi.org/10.1134/s096554252208005x

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Dorodnicyn Computing Center, Federal Research Center \u201cComputer Science and Control\u201d, Russian Academy of Sciences, 119333, Moscow, Russia", 
            "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garanzha", 
        "givenName": "V. A.", 
        "id": "sg:person.011314573365.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011314573365.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Dorodnicyn Computing Center, Federal Research Center \u201cComputer Science and Control\u201d, Russian Academy of Sciences, 119333, Moscow, Russia", 
            "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kudryavtseva", 
        "givenName": "L. N.", 
        "id": "sg:person.012112153765.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012112153765.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia", 
          "id": "http://www.grid.ac/institutes/grid.18763.3b", 
          "name": [
            "Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kamenski", 
        "givenName": "L.", 
        "id": "sg:person.014376440053.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014376440053.88"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1134/s096554251912008x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1124951863", 
          "https://doi.org/10.1134/s096554251912008x"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-030-23436-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1121647174", 
          "https://doi.org/10.1007/978-3-030-23436-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1134/s0965542519120078", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1124956782", 
          "https://doi.org/10.1134/s0965542519120078"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02187681", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015637565", 
          "https://doi.org/10.1007/bf02187681"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-08", 
    "datePublishedReg": "2022-08-01", 
    "description": "We consider the construction of a polyhedral Delaunay partition as a limit of the sequence of power diagrams (in Russian traditionally called radical partitions), while the dual Voronoi diagram is obtained as a limit of the sequence of weighted Delaunay partitions. Using a lifting analogy, this problem is reduced to the construction of a pair of dual convex polyhedra, inscribed and superscribed around a circular paraboloid, as a limit of the sequence of pairs of general dual convex polyhedra. The sequence of primal polyhedra should converge to the superscribed polyhedron, while the sequence of dual polyhedra converges to the inscribed polyhedron. For building sequences of dual polyhedra we are mostly interested in the case when the vertices of primal polyhedra can move or merge together. This means that no new faces are allowed for dual polyhedra. These rules essentially define the transformation of the set of initial spheres defining a power diagram into the set of Delaunay spheres using sphere movement, radius variation, and sphere elimination as admissible operations. Although a rigorous foundation (existence theorems) for this problem is still unavailable, we suggest a functional measuring the deviation of the convex polyhedron from the one inscribed into the paraboloid. This functional is the discrete Dirichlet functional for the power function (power of a point with respect to a ball) which is a linear interpolant of the vertical distance of the dual vertices from the paraboloid. The absolute minimizer of this functional is attained on the constant power field, meaning that the inscribed polyhedron can be obtained using a simple translation. This formulation of the Dirichlet functional for the dual surface is not quadratic since the unknowns are the vertices of the primal polyhedron. Hence, the transformation of the set of spheres into Delaunay spheres is not unique. In this work, we concentrate on the experimental confirmation of the viability of suggested approach and put aside mesh quality problems. The zero value of the gradient of the proposed functional defines a manifold describing the evolution of Delaunay spheres. Hence, Delaunay\u2013Voronoi meshes can be optimized using this manifold as a constraint. Numerical examples illustrate polygonal Delaunay meshing in planar domains.", 
    "genre": "article", 
    "id": "sg:pub.10.1134/s096554252208005x", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136025", 
        "issn": [
          "0965-5425", 
          "1555-6662"
        ], 
        "name": "Computational Mathematics and Mathematical Physics", 
        "publisher": "Pleiades Publishing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "8", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "62"
      }
    ], 
    "keywords": [
      "Delaunay partition", 
      "power diagram", 
      "convex polyhedra", 
      "circular paraboloid", 
      "sequence of pairs", 
      "dual polyhedron", 
      "rigorous foundation", 
      "Dirichlet functional", 
      "linear interpolant", 
      "dual vertex", 
      "set of spheres", 
      "numerical examples", 
      "partition", 
      "limit", 
      "diagram", 
      "dual Voronoi diagram", 
      "Voronoi diagram", 
      "problem", 
      "polyhedra", 
      "paraboloid", 
      "converges", 
      "vertices", 
      "set", 
      "initial sphere", 
      "sphere", 
      "Delaunay spheres", 
      "sphere movement", 
      "admissible operations", 
      "functionals", 
      "power function", 
      "interpolants", 
      "absolute minimizer", 
      "minimizers", 
      "simple translation", 
      "formulation", 
      "dual surface", 
      "unknowns", 
      "experimental confirmation", 
      "manifold", 
      "mesh", 
      "constraints", 
      "Delaunay", 
      "planar domains", 
      "meshing", 
      "approximation", 
      "construction", 
      "sequence", 
      "analogy", 
      "pairs", 
      "cases", 
      "rules", 
      "transformation", 
      "variation", 
      "operation", 
      "foundation", 
      "deviation", 
      "one", 
      "function", 
      "vertical distance", 
      "distance", 
      "field", 
      "surface", 
      "work", 
      "approach", 
      "quality problems", 
      "values", 
      "gradient", 
      "defines", 
      "evolution", 
      "domain", 
      "Delaunay meshing", 
      "new face", 
      "face", 
      "movement", 
      "elimination", 
      "power field", 
      "translation", 
      "confirmation", 
      "viability", 
      "example"
    ], 
    "name": "Non-Simplicial Delaunay Meshing via Approximation by Radical Partitions", 
    "pagination": "1203-1216", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1150918513"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1134/s096554252208005x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1134/s096554252208005x", 
      "https://app.dimensions.ai/details/publication/pub.1150918513"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T21:09", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_947.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1134/s096554252208005x"
  }
]
 

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.1134/s096554252208005x'

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.1134/s096554252208005x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1134/s096554252208005x'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1134/s096554252208005x'


 

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

168 TRIPLES      21 PREDICATES      109 URIs      97 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1134/s096554252208005x schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Ncc3ef34669bc48369b78ae3433edf1e4
4 schema:citation sg:pub.10.1007/978-3-030-23436-2
5 sg:pub.10.1007/bf02187681
6 sg:pub.10.1134/s0965542519120078
7 sg:pub.10.1134/s096554251912008x
8 schema:datePublished 2022-08
9 schema:datePublishedReg 2022-08-01
10 schema:description We consider the construction of a polyhedral Delaunay partition as a limit of the sequence of power diagrams (in Russian traditionally called radical partitions), while the dual Voronoi diagram is obtained as a limit of the sequence of weighted Delaunay partitions. Using a lifting analogy, this problem is reduced to the construction of a pair of dual convex polyhedra, inscribed and superscribed around a circular paraboloid, as a limit of the sequence of pairs of general dual convex polyhedra. The sequence of primal polyhedra should converge to the superscribed polyhedron, while the sequence of dual polyhedra converges to the inscribed polyhedron. For building sequences of dual polyhedra we are mostly interested in the case when the vertices of primal polyhedra can move or merge together. This means that no new faces are allowed for dual polyhedra. These rules essentially define the transformation of the set of initial spheres defining a power diagram into the set of Delaunay spheres using sphere movement, radius variation, and sphere elimination as admissible operations. Although a rigorous foundation (existence theorems) for this problem is still unavailable, we suggest a functional measuring the deviation of the convex polyhedron from the one inscribed into the paraboloid. This functional is the discrete Dirichlet functional for the power function (power of a point with respect to a ball) which is a linear interpolant of the vertical distance of the dual vertices from the paraboloid. The absolute minimizer of this functional is attained on the constant power field, meaning that the inscribed polyhedron can be obtained using a simple translation. This formulation of the Dirichlet functional for the dual surface is not quadratic since the unknowns are the vertices of the primal polyhedron. Hence, the transformation of the set of spheres into Delaunay spheres is not unique. In this work, we concentrate on the experimental confirmation of the viability of suggested approach and put aside mesh quality problems. The zero value of the gradient of the proposed functional defines a manifold describing the evolution of Delaunay spheres. Hence, Delaunay–Voronoi meshes can be optimized using this manifold as a constraint. Numerical examples illustrate polygonal Delaunay meshing in planar domains.
11 schema:genre article
12 schema:isAccessibleForFree true
13 schema:isPartOf N3175c4a2820c47da9cff22969b3f8b95
14 N89b1775a465a4f3e8f8d5b0b9510e7d8
15 sg:journal.1136025
16 schema:keywords Delaunay
17 Delaunay meshing
18 Delaunay partition
19 Delaunay spheres
20 Dirichlet functional
21 Voronoi diagram
22 absolute minimizer
23 admissible operations
24 analogy
25 approach
26 approximation
27 cases
28 circular paraboloid
29 confirmation
30 constraints
31 construction
32 converges
33 convex polyhedra
34 defines
35 deviation
36 diagram
37 distance
38 domain
39 dual Voronoi diagram
40 dual polyhedron
41 dual surface
42 dual vertex
43 elimination
44 evolution
45 example
46 experimental confirmation
47 face
48 field
49 formulation
50 foundation
51 function
52 functionals
53 gradient
54 initial sphere
55 interpolants
56 limit
57 linear interpolant
58 manifold
59 mesh
60 meshing
61 minimizers
62 movement
63 new face
64 numerical examples
65 one
66 operation
67 pairs
68 paraboloid
69 partition
70 planar domains
71 polyhedra
72 power diagram
73 power field
74 power function
75 problem
76 quality problems
77 rigorous foundation
78 rules
79 sequence
80 sequence of pairs
81 set
82 set of spheres
83 simple translation
84 sphere
85 sphere movement
86 surface
87 transformation
88 translation
89 unknowns
90 values
91 variation
92 vertical distance
93 vertices
94 viability
95 work
96 schema:name Non-Simplicial Delaunay Meshing via Approximation by Radical Partitions
97 schema:pagination 1203-1216
98 schema:productId N3d0a3521d57e4688a2add81803e8daf3
99 N6acda48118204f72a2fc339cc36e4659
100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1150918513
101 https://doi.org/10.1134/s096554252208005x
102 schema:sdDatePublished 2022-11-24T21:09
103 schema:sdLicense https://scigraph.springernature.com/explorer/license/
104 schema:sdPublisher Nd13b02c31bfd49568fe6cb7423561a19
105 schema:url https://doi.org/10.1134/s096554252208005x
106 sgo:license sg:explorer/license/
107 sgo:sdDataset articles
108 rdf:type schema:ScholarlyArticle
109 N3175c4a2820c47da9cff22969b3f8b95 schema:volumeNumber 62
110 rdf:type schema:PublicationVolume
111 N3d0a3521d57e4688a2add81803e8daf3 schema:name dimensions_id
112 schema:value pub.1150918513
113 rdf:type schema:PropertyValue
114 N622502f70b3b430182359f16154fe430 rdf:first sg:person.014376440053.88
115 rdf:rest rdf:nil
116 N6acda48118204f72a2fc339cc36e4659 schema:name doi
117 schema:value 10.1134/s096554252208005x
118 rdf:type schema:PropertyValue
119 N89b1775a465a4f3e8f8d5b0b9510e7d8 schema:issueNumber 8
120 rdf:type schema:PublicationIssue
121 Ncc3ef34669bc48369b78ae3433edf1e4 rdf:first sg:person.011314573365.15
122 rdf:rest Nd79d1ae175c442e5ad2edceed80d3acb
123 Nd13b02c31bfd49568fe6cb7423561a19 schema:name Springer Nature - SN SciGraph project
124 rdf:type schema:Organization
125 Nd79d1ae175c442e5ad2edceed80d3acb rdf:first sg:person.012112153765.45
126 rdf:rest N622502f70b3b430182359f16154fe430
127 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
128 schema:name Mathematical Sciences
129 rdf:type schema:DefinedTerm
130 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
131 schema:name Applied Mathematics
132 rdf:type schema:DefinedTerm
133 sg:journal.1136025 schema:issn 0965-5425
134 1555-6662
135 schema:name Computational Mathematics and Mathematical Physics
136 schema:publisher Pleiades Publishing
137 rdf:type schema:Periodical
138 sg:person.011314573365.15 schema:affiliation grid-institutes:grid.18763.3b
139 schema:familyName Garanzha
140 schema:givenName V. A.
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011314573365.15
142 rdf:type schema:Person
143 sg:person.012112153765.45 schema:affiliation grid-institutes:grid.18763.3b
144 schema:familyName Kudryavtseva
145 schema:givenName L. N.
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012112153765.45
147 rdf:type schema:Person
148 sg:person.014376440053.88 schema:affiliation grid-institutes:grid.18763.3b
149 schema:familyName Kamenski
150 schema:givenName L.
151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014376440053.88
152 rdf:type schema:Person
153 sg:pub.10.1007/978-3-030-23436-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1121647174
154 https://doi.org/10.1007/978-3-030-23436-2
155 rdf:type schema:CreativeWork
156 sg:pub.10.1007/bf02187681 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015637565
157 https://doi.org/10.1007/bf02187681
158 rdf:type schema:CreativeWork
159 sg:pub.10.1134/s0965542519120078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1124956782
160 https://doi.org/10.1134/s0965542519120078
161 rdf:type schema:CreativeWork
162 sg:pub.10.1134/s096554251912008x schema:sameAs https://app.dimensions.ai/details/publication/pub.1124951863
163 https://doi.org/10.1134/s096554251912008x
164 rdf:type schema:CreativeWork
165 grid-institutes:grid.18763.3b schema:alternateName Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia
166 schema:name Dorodnicyn Computing Center, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences, 119333, Moscow, Russia
167 Moscow Institute of Physics and Technology (State University), 141701, Dolgoprudnyi, Moscow oblast, Russia
168 rdf:type schema:Organization
 




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


...