Mixing
What does the non-embedded graph derived from a Delaunay triangulation imply about the relative spatial...
up vote
0
down vote
favorite
Let $p_{k (k in K)}in P$ be a tuple in the space $X$, a real coordinate plane in ${rm I!R}^{2}$ with a Euclidean distance function $d$ and $K$ is a set of indices. The set of tuples $P$ are Poisson distributed and of finite number distributed within a circle residing in $X$. The points can be used to define a Voronoi tessellation according to:
begin{equation}
s_k = { x in X | d(x, p_k) leq d(x, p_j) , forall , j , neq k }
end{equation}
where each $s_k in S$ is a set of points that are closest to a corresponding Voronoi center $p_k$ ie a facet of the tessellation. The corresponding Delaunay triangulation $DT(S)$ is the set of points $p_k$ and edges $E$ satisfying the empty circle property that no circumcircle of any triangle in $DT(S)$ has a point of $P$ in its interior.
Now say we have limited knowledge about $DT(S)$, and that we only have access to a non-embedded graph $G = (K,E)$ derived from $DT(S)$ i.e. the set of vertices denoted by their indices and edges minus all real coordinate information of $P$. Let us say we also know the boundary geometry and that the points $P$ are Poisson distribution within a circle. What is the strongest inference that can be made regarding Euclidean metrics and the points $P$ given knowledge of this limited set $G$ and boundary conditions?
To be more specific, let ${ k_0, k_N, k_{N-1} } subseteq K$ be any subset of three vertices in $K$ that satisfies the property that $k_N$ has at least one geodesic shortest path (i.e. hop count or number of edges) leading to a so-called origin $k_0$ equal to $N$ steps, and let $k_{N-1}$ be a vertex located on a geodesic shortest path to $k_N$ with its own geodesic shortest path to $k_0$ equal to $N-1$ steps. Let the set ${ p_{k_0},p_{k_N},p_{k_{N-1}} } subseteq P$ be the corresponding set of real coordinate points in $DT(S)$ in ${rm I!R}^{2}$.
Can it be proved that
begin{equation}
exists , k_{N-1} | d(p_{k_0},p_{k_N}) > d(p_{k_0},p_{k_{N-1}}) forall k_0, k_N in K.
end{equation}
In otherwords, for any two vertices in the non-embedded graph $G$ with a $N$ length geodesic shortest path distance, is there a vertex along that shortest path with $N-1$ geodesic distance that is also closer to the origin in Euclidean distance?
The context is that I am interested in establishing an inferential rule or upper/lower bound regarding the relative locations of points in $P$ or $DT(S)$ in terms of Euclidean metrics given only knowledge of $G = (K,E)$ since, afterall $G$ is derived from $DT(S)$ and thus coupled to Euclidean metrics in this way.
Thank you in advance for your help!
graph-theory metric-spaces planar-graph tessellations measurement-theory
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
Let $p_{k (k in K)}in P$ be a tuple in the space $X$, a real coordinate plane in ${rm I!R}^{2}$ with a Euclidean distance function $d$ and $K$ is a set of indices. The set of tuples $P$ are Poisson distributed and of finite number distributed within a circle residing in $X$. The points can be used to define a Voronoi tessellation according to:
begin{equation}
s_k = { x in X | d(x, p_k) leq d(x, p_j) , forall , j , neq k }
end{equation}
where each $s_k in S$ is a set of points that are closest to a corresponding Voronoi center $p_k$ ie a facet of the tessellation. The corresponding Delaunay triangulation $DT(S)$ is the set of points $p_k$ and edges $E$ satisfying the empty circle property that no circumcircle of any triangle in $DT(S)$ has a point of $P$ in its interior.
Now say we have limited knowledge about $DT(S)$, and that we only have access to a non-embedded graph $G = (K,E)$ derived from $DT(S)$ i.e. the set of vertices denoted by their indices and edges minus all real coordinate information of $P$. Let us say we also know the boundary geometry and that the points $P$ are Poisson distribution within a circle. What is the strongest inference that can be made regarding Euclidean metrics and the points $P$ given knowledge of this limited set $G$ and boundary conditions?
To be more specific, let ${ k_0, k_N, k_{N-1} } subseteq K$ be any subset of three vertices in $K$ that satisfies the property that $k_N$ has at least one geodesic shortest path (i.e. hop count or number of edges) leading to a so-called origin $k_0$ equal to $N$ steps, and let $k_{N-1}$ be a vertex located on a geodesic shortest path to $k_N$ with its own geodesic shortest path to $k_0$ equal to $N-1$ steps. Let the set ${ p_{k_0},p_{k_N},p_{k_{N-1}} } subseteq P$ be the corresponding set of real coordinate points in $DT(S)$ in ${rm I!R}^{2}$.
Can it be proved that
begin{equation}
exists , k_{N-1} | d(p_{k_0},p_{k_N}) > d(p_{k_0},p_{k_{N-1}}) forall k_0, k_N in K.
end{equation}
In otherwords, for any two vertices in the non-embedded graph $G$ with a $N$ length geodesic shortest path distance, is there a vertex along that shortest path with $N-1$ geodesic distance that is also closer to the origin in Euclidean distance?
The context is that I am interested in establishing an inferential rule or upper/lower bound regarding the relative locations of points in $P$ or $DT(S)$ in terms of Euclidean metrics given only knowledge of $G = (K,E)$ since, afterall $G$ is derived from $DT(S)$ and thus coupled to Euclidean metrics in this way.
Thank you in advance for your help!
graph-theory metric-spaces planar-graph tessellations measurement-theory
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let $p_{k (k in K)}in P$ be a tuple in the space $X$, a real coordinate plane in ${rm I!R}^{2}$ with a Euclidean distance function $d$ and $K$ is a set of indices. The set of tuples $P$ are Poisson distributed and of finite number distributed within a circle residing in $X$. The points can be used to define a Voronoi tessellation according to:
begin{equation}
s_k = { x in X | d(x, p_k) leq d(x, p_j) , forall , j , neq k }
end{equation}
where each $s_k in S$ is a set of points that are closest to a corresponding Voronoi center $p_k$ ie a facet of the tessellation. The corresponding Delaunay triangulation $DT(S)$ is the set of points $p_k$ and edges $E$ satisfying the empty circle property that no circumcircle of any triangle in $DT(S)$ has a point of $P$ in its interior.
Now say we have limited knowledge about $DT(S)$, and that we only have access to a non-embedded graph $G = (K,E)$ derived from $DT(S)$ i.e. the set of vertices denoted by their indices and edges minus all real coordinate information of $P$. Let us say we also know the boundary geometry and that the points $P$ are Poisson distribution within a circle. What is the strongest inference that can be made regarding Euclidean metrics and the points $P$ given knowledge of this limited set $G$ and boundary conditions?
To be more specific, let ${ k_0, k_N, k_{N-1} } subseteq K$ be any subset of three vertices in $K$ that satisfies the property that $k_N$ has at least one geodesic shortest path (i.e. hop count or number of edges) leading to a so-called origin $k_0$ equal to $N$ steps, and let $k_{N-1}$ be a vertex located on a geodesic shortest path to $k_N$ with its own geodesic shortest path to $k_0$ equal to $N-1$ steps. Let the set ${ p_{k_0},p_{k_N},p_{k_{N-1}} } subseteq P$ be the corresponding set of real coordinate points in $DT(S)$ in ${rm I!R}^{2}$.
Can it be proved that
begin{equation}
exists , k_{N-1} | d(p_{k_0},p_{k_N}) > d(p_{k_0},p_{k_{N-1}}) forall k_0, k_N in K.
end{equation}
In otherwords, for any two vertices in the non-embedded graph $G$ with a $N$ length geodesic shortest path distance, is there a vertex along that shortest path with $N-1$ geodesic distance that is also closer to the origin in Euclidean distance?
The context is that I am interested in establishing an inferential rule or upper/lower bound regarding the relative locations of points in $P$ or $DT(S)$ in terms of Euclidean metrics given only knowledge of $G = (K,E)$ since, afterall $G$ is derived from $DT(S)$ and thus coupled to Euclidean metrics in this way.
Thank you in advance for your help!
graph-theory metric-spaces planar-graph tessellations measurement-theory
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Let $p_{k (k in K)}in P$ be a tuple in the space $X$, a real coordinate plane in ${rm I!R}^{2}$ with a Euclidean distance function $d$ and $K$ is a set of indices. The set of tuples $P$ are Poisson distributed and of finite number distributed within a circle residing in $X$. The points can be used to define a Voronoi tessellation according to:
begin{equation}
s_k = { x in X | d(x, p_k) leq d(x, p_j) , forall , j , neq k }
end{equation}
where each $s_k in S$ is a set of points that are closest to a corresponding Voronoi center $p_k$ ie a facet of the tessellation. The corresponding Delaunay triangulation $DT(S)$ is the set of points $p_k$ and edges $E$ satisfying the empty circle property that no circumcircle of any triangle in $DT(S)$ has a point of $P$ in its interior.
Now say we have limited knowledge about $DT(S)$, and that we only have access to a non-embedded graph $G = (K,E)$ derived from $DT(S)$ i.e. the set of vertices denoted by their indices and edges minus all real coordinate information of $P$. Let us say we also know the boundary geometry and that the points $P$ are Poisson distribution within a circle. What is the strongest inference that can be made regarding Euclidean metrics and the points $P$ given knowledge of this limited set $G$ and boundary conditions?
To be more specific, let ${ k_0, k_N, k_{N-1} } subseteq K$ be any subset of three vertices in $K$ that satisfies the property that $k_N$ has at least one geodesic shortest path (i.e. hop count or number of edges) leading to a so-called origin $k_0$ equal to $N$ steps, and let $k_{N-1}$ be a vertex located on a geodesic shortest path to $k_N$ with its own geodesic shortest path to $k_0$ equal to $N-1$ steps. Let the set ${ p_{k_0},p_{k_N},p_{k_{N-1}} } subseteq P$ be the corresponding set of real coordinate points in $DT(S)$ in ${rm I!R}^{2}$.
Can it be proved that
begin{equation}
exists , k_{N-1} | d(p_{k_0},p_{k_N}) > d(p_{k_0},p_{k_{N-1}}) forall k_0, k_N in K.
end{equation}
In otherwords, for any two vertices in the non-embedded graph $G$ with a $N$ length geodesic shortest path distance, is there a vertex along that shortest path with $N-1$ geodesic distance that is also closer to the origin in Euclidean distance?
The context is that I am interested in establishing an inferential rule or upper/lower bound regarding the relative locations of points in $P$ or $DT(S)$ in terms of Euclidean metrics given only knowledge of $G = (K,E)$ since, afterall $G$ is derived from $DT(S)$ and thus coupled to Euclidean metrics in this way.
Thank you in advance for your help!
graph-theory metric-spaces planar-graph tessellations measurement-theory
graph-theory metric-spaces planar-graph tessellations measurement-theory
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
Entangler
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 21 hours ago
Entangler
64
asked 21 hours ago
Entangler
64
64
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3004796%2fwhat-does-the-non-embedded-graph-derived-from-a-delaunay-triangulation-imply-abo%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
