https://visone.ethz.ch/wiki/api.php?action=feedcontributions&user=Muellerj&feedformat=atomvisone manual - User contributions [en]2024-03-29T09:09:02ZUser contributionsMediaWiki 1.39.6https://visone.ethz.ch/wiki/index.php?title=Stochastic_blockmodel&diff=1697Stochastic blockmodel2023-05-25T14:00:50Z<p>Muellerj: Created page with "'''Stochastic blockmodels''' are a kind of statistical model for networks based on partitioning the nodes into clusters and describing the distribution of links between any tw..."</p>
<hr />
<div>'''Stochastic blockmodels''' are a kind of statistical model for networks based on partitioning the nodes into clusters and describing the distribution of links between any two clusters.<br />
<br />
Visone supports the sampling of networks from some kinds of stochastic blockmodels. The user interface makes the sampler available in two ways:<br />
<br />
* In the network creation dialog accessible via the file menu, where the stochastic blockmodel can be specified by supplying a matrix of (manually entered) edge weights.<br />
* In the transformation tab under the name "SBM sampling", where the blockmodel is specified by the currently active network and its attributes.<br />
<br />
== Sampling in the network creation dialog ==<br />
<br />
In the network creation dialog, the following settings are offered to specify the sampling from a stochastic blockmodel:<br />
* '''Cluster count''' sets the number of clusters in the blockmodel.<br />
* '''Model''' sets the underlying type of statistical model/distribution used for sampling the edges in the block<br />
* '''Directed''' sets whether the blockmodel is used to sample a directed or undirected network.<br />
* '''Loops''' sets whether the sampled network may contain loops or not.<br />
* '''Cluster sizes''' specifies the number of vertices for each individual cluster. If the cluster size for a specific cluster is not set explicitly, then the '''default cluster size''' is used instead.<br />
* '''Block weights''' specifies the weights used to parameterize the underlying statistical model/distribution. The interpretation of this weight depends on the specific statistical model (see the list of models below). If the weight for a specific block is not explicitly set, then the '''default block weight''' is used instead.<br />
<br />
After pressing "apply", a new network generated from the specified blockmodel is made available in a new tab.<br />
<br />
== Sampling in the transformation tab ==<br />
<br />
In the transformation tab, the stochastic blockmodel is derived from the currently active network. Each node in the network describes a cluster, and each edge describes a block. The edge direction determines the direction of the edges sampled from it. Note that the currently active network can have multiple edges between two nodes describing clusters; in this case, the sampling from these edges proceeds independently.<br />
<br />
Besides the network itself, the following settings are offered to specify the sampline:<br />
<br />
* '''Model''' determines the underlying type of statistical model/distribution used for sampling the edges in the newly generated network.<br />
* '''Cluster sizes''' is an attribute on the nodes in the active network and determines how many nodes are generated for each cluster.<br />
* '''Cluster labels''' is an attribute on the nodes in the active network and is used to create a node attribute ''cluster'' in the newly generated network to label the new nodes according to their cluster membership. If no node attribute is specified, then sequential labels are used instead.<br />
* '''Edge labels''' is an attribute on the edges in the active network and is used to create an edge attribute ''block'' in the newly generated network to label the new edges according to which block they were generated from. If no edge attribute is specified, then sequential labels are used instead.<br />
* '''Block weights''' are weights on the blocks/edges in the active network to parameterize the statistical model. The interpretation of this weight depends on the specific statistical model (see the list of models below).<br />
* '''Loops''' sets whether self-loops are allowed in the generated network. Loops can be allowed or forbidden for all blocks, or a Boolean edge attribute can be used to set this for each block individually.<br />
<br />
After pressing "transform", a new network generated from the specified blockmodel is made available in a new tab.<br />
<br />
== Statistical models ==<br />
<br />
Assume we are sampling the edges in a block from cluster <math>C</math> to <math>C'</math> with block weight <math>w</math>.<br />
Currently, visone supports sampling of the edges in the blocks from the following distributions:<br />
<br />
* '''Bernoulli''': Edges between different pairs of vertices are drawn independently. The block weight specifies the probability that a specific edge exists or not, i.e., each edge is sampled with probability <math>w</math>.<br />
* '''Geometric''': Edges between different pairs of vertices are drawn independently. The block weight specifies the expected number of parallel edges between any two nodes in the clusters. Parallel edges are sampled from a Geometric distribution: <math>k</math> parallel edges from a vertex in <math>C</math> to a vertex in <math>C'</math> have probability <math>\left(\frac{w}{1+w}\right)^k \frac{1}{1+w}</math>.<br />
* '''Poisson''': Edges between different pairs of vertices are drawn independently. The block weight specifies the expected number of parallel edges between any two nodes in the clusters. Parallel edges are sampled from a Poisson distribution: <math>k</math> parallel edges from a vertex in <math>C</math> to a vertex in <math>C'</math> have probability <math>\frac{w^k}{k!}e^{-w}</math>.<br />
* '''Configuration model''' (or random sequence model): The block weight specifies the number of edges within the block. The edges are drawn in line with the random sequence model introduced in [https://doi.org/10.1016/S0304-0208(08)73611-9 Bollobás, B., and Frieze, A.M. (1985). On matchings and Hamiltonian cycles in random graphs. Annals of Discrete Mathematics 28:23–46.] and [https://doi.org/10.1002/rsa.3240020103 Chvátal, V. (1991). Almost all graphs with 1.44n edges are 3-colorable. Random Structures & Algorithms 2(1):11–28.]<br/>The model works as follows: A sequence of <math>w</math> ordered pairs of vertices is drawn. For each pair, an edge is created, where the first vertex defines the source and the second the target of the edge. <br/> Assume that matrix <math>A \in \mathbb{N}^{C \times C'}</math> describes the number of parallel edges from vertices in <math>C</math> to vertices in <math>C'</math> in the block and the number of edges in the block is <math>w</math>. The statistical model translates into the following probabilities (note that in all cases, the probability scales with factor <math>\frac{1}{k!}</math> for an edge with multiplicity <math>k</math>):<br />
** If the block is off the diagonal or directed with loops allowed, then the probability is <math>\frac{w!}{|C|^w|C'|^w\prod_{u \in C, v \in C'} A_{uv}!}</math>.<br />
** If the block is directed, on the diagonal and loops are forbidden, then the probability is <math>\frac{w!}{|C|^{w}(|C|-1)^w\prod_{u, v \in C: u \neq v} A_{uv}!}</math>.<br />
** If the block is undirected, on the diagonal and loops are allowed, then the probability is <math>\frac{2^ww!}{|C|^{2w}\prod_{u, v \in C: u \leq v} A_{uv}! \prod_{v \in C} 2^{A_{vv}}}</math> for some ordering <math>\leq</math> on the vertices. Note that this means that loops are half as likely as non-loops.<br />
** If the block is undirected, on the diagonal and loops are forbidden, then the probability is <math>\frac{2^ww!}{|C|^{w}(|C|-1)^w\prod_{u, v \in C: u < v} A_{uv}!}</math> for some strict ordering <math><</math> on the vertices.<br />
* '''Configuration model (no multi-edges)''': This is like the multigraph model above, but with the difference that multi-edges are not allowed. This means that it is equivalent to the Erdős–Rényi <math>\mathcal G(n, m)</math> model if loops are not permitted.<br />
<br />
== Time complexity ==<br />
<br />
A network is generated in time linear in the size of the sampled network.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1696Delaunay triangulation2023-05-25T13:05:37Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> was originally defined in [https://doi.org/10.1016/S0020-0190(99)00107-6 Abellanas et al. (1999), Structural tolerance and Delaunay triangulation. Information Processing Letters 71(5–6):221–227]. It is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute (while the values assigned to pre-existing edges are left unchanged).</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1695Delaunay triangulation2023-05-25T13:04:06Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> was originally defined in [https://doi.org/10.1016/S0020-0190(99)00107-6 Abellanas et al. (1999), Structural tolerance and Delaunay triangulation. Information Processing Letters 71(5–6):221–227]. It is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1694Delaunay triangulation2023-05-24T11:10:06Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
For the original definition of the distance stability, see [https://doi.org/10.1016/S0020-0190(99)00107-6 Abellanas et al. (1999), Structural tolerance and Delaunay triangulation. Information Processing Letters 71(5–6):221–227]<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1693Delaunay triangulation2023-05-24T11:09:41Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs. Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
For the original definition of the distance stability, see [https://doi.org/10.1016/S0020-0190(99)00107-6 Abellannas et al. (1999), Structural tolerance and Delaunay triangulation. Information Processing Letters 71(5–6):221–227]<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1692Delaunay triangulation2023-05-24T11:04:26Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>(|\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1691Delaunay triangulation2023-05-24T11:03:59Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as <math>|(\overline{CR}|-|\overline{CP}|)/2</math>, i.e., half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1690Delaunay triangulation2023-05-24T11:01:32Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as half the difference in radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> to the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by half the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1689Delaunay triangulation2023-05-24T10:59:10Z<p>Muellerj: </p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendicular bisectors of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as the radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> minus the radius of the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=Delaunay_triangulation&diff=1688Delaunay triangulation2023-05-24T10:50:06Z<p>Muellerj: Created page with "The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The..."</p>
<hr />
<div>The '''Delaunay triangulation''' of points <math>P</math> is a triangulation of <math>P</math> such that no point in <math>P</math> lies in the circumcircle of a triangle. The Delaunay triangulation is the dual of the Voronoi diagram.<br />
<br />
== Stability measures ==<br />
<br />
visone computes two stability measures on Delaunay edges. Smaller values of these measures mean less change is needed to the coordinates of nearby points for the edge to vanish in the triangulation.<br />
<br />
The stability measures are the following:<br />
* The angular stability of a Delaunay edge <math>PQ</math> is the angle <math>\alpha</math> at which the end points of the Delaunay edges see the dual Voronoi edge. That is, if <math>PQR</math> and <math>PQS</math> are the Delaunay triangles incident to the edge <math>PQ</math>, then <math>\alpha = \pi - \angle PRQ - \angle PSQ</math>; if <math>PQ</math> is on the convex hull, then <math>\alpha = \pi - \angle PRQ</math> given the only incident Delaunay triangle <math>PQR</math>. For the original definition of this stability measure and a discussion of its properties, see [https://doi.org/10.1007/s00454-015-9730-x Agarwal et al. (2015), Stable Delaunay Graphs, Discrete & Computational Geometry 54:905–929].<br />
* The distance stability of a Delaunay edge <math>PQ</math> is computed as follows:<br />
** If the Delaunay edge has two incident Delaunay triangles <math>PQR</math> and <math>PQS</math>, then let <math>C</math> be the intersection point of the perpendiculars of <math>PQ</math> and <math>RS</math>. The distance stability of a Delaunay edge <math>PQ</math> is defined as the radius of the circle centered at <math>C</math> and passing through <math>R</math> and <math>S</math> minus the radius of the circle centered at <math>C</math> and passing through <math>P</math> and <math>Q</math>.<br />
** If the Delaunay edge <math>PQ</math> of triangle <math>PQR</math> is located on the convex hull, the distance stability is given by the distance of <math>R</math> from the edge <math>PQ</math>.<br />
<br />
Note that the angular stability is invariant to rescaling of the coordinates by a factor <math>\beta > 0</math>, while the distance stability scales linearly.<br />
<br />
== Result ==<br />
<br />
visone computes the Delaunay triangulation of a set of points described by the given nodes in a network, plus the stability measures computed on each Delaunay edge. If desired, pre-existing edges in the network can be removed, and unstable Delaunay edges whose stability measures are below given thresholds can be elided. Moreover, newly created Delaunay edges are assigned the value true in a specified Boolean edge attribute.</div>Muellerjhttps://visone.ethz.ch/wiki/index.php?title=MediaWiki:Sidebar&diff=1687MediaWiki:Sidebar2022-02-14T18:13:43Z<p>Muellerj: Web applet version of visone no longer exists</p>
<hr />
<div>* Navigation<br />
** mainpage|mainpage-description<br />
** recentchanges-url|recentchanges<br />
* Links<br />
** http://visone.info|visone home<br />
<!-- ** portal-url|portal --><br />
<!-- ** currentevents-url|currentevents --><br />
<!-- ** randompage-url|randompage --><br />
<!-- ** helppage|help --><br />
* SEARCH<br />
* TOOLBOX<br />
<!-- * LANGUAGES --></div>Muellerj