3

Let suppose I have a Delaunay triangulation with $n$ triangles, and K distinct colours. I want to color each triangle such that if I start from one triangle with color k, i can reach all triangles with the same color, without passing on triangles with colors different from k. I can move from one triangle to another if they share an edge.

I want to know if there is a way to determine all possible combinations of this colored triangulation, and for each combination I'm only interested in the number of triangles that have a specific color.

For example, I just want to know that there are

  • 2 combinations with 3 color_1, 2 color_2 and 10 color_3

  • 10 combinations with 3 color_1 11 color_2 and 1 color_3 etc...

Is that possible? Even a reference it's super helpful!

Thanks.

Edit: The color is inside the triangles

Edit 2: I can move from a triangle that is colored with the k-th color, to another one, only if it has the same color and they have an edge in common

niandra82
  • 1,160
  • 8
  • 24
  • 1
    Are you coloring edges or triangles of edges? Can each edge only carry a single color? If yes, I do not understand how triangles of different colors can share an edge. It would help, if you plot an example. – cdalitz Oct 23 '20 at 19:20
  • I’m coloring the inside of the triangle – niandra82 Oct 23 '20 at 23:09
  • This is not an easy problem. What do you need it for? Maybe the answer to that helps to think of acceptable approximate solutions. – Sextus Empiricus Nov 19 '20 at 14:50
  • @SextusEmpiricus My need is more general. I have a two dimensional space $D \subset \mathbb{R}^2$ (not based on a triangulation, but a general space). I need to derive a way to divided it in K connected regions, and assign a probability to each possible way I can do it. I thought that using a discretisation of the space, like a triangulation, and then using a Markov model (similar to the Ising), would be easier, but I'm starting to think it is not. That's why i need a way to compute all possible combinations. – niandra82 Nov 20 '20 at 12:02
  • "I need to derive a way to divided it in K connected regions, and assign a probability to each possible way I can do it." Why is it that you need the probability for these and how do you define probability for these cases? – Sextus Empiricus Nov 20 '20 at 12:29
  • @SextusEmpiricus It is a problem of spatial clustering, that is hard to explain in few words. With a Delaunay triangulation (or any spatial discretization), you can define this probabilities using Brook's lemma. There are different way to do that, but probably one of the easier is to set the probability that a triangle have a specific color proportional to the number of neighbours that have that same color, or something similar – niandra82 Nov 20 '20 at 12:36
  • @niandra82 I think that it is also hard to find an exact solution (let alone describe it in a few words). This problem really needs to be simplified (but how it not so clear. Would an approximate algorithm or Monte Carlo approach be ok? Would a solution for a, simpler, square grid be ok? Etc?). Maybe it is easier to explain the underlying problem such that the problem can be correctly simplified. For example: if your goal is just to eventually know the probability for each triangle/region to have some particular colour, then I would try to tackle this by a Monte Carlo simulation. – Sextus Empiricus Nov 20 '20 at 13:09
  • @SextusEmpiricus Yes, I know it is hard to find a solution. Unfortunately, Monte Carlo simulation are not useful since I need this as property of a Bayesian model. – niandra82 Nov 20 '20 at 16:22
  • @niandra82 can you explain more about that. – Sextus Empiricus Nov 20 '20 at 16:55
  • @SextusEmpiricus Very simplified version, based on the triangulation: $y(\mathbf{s}) \sim N(\mu_{z(\mathbf{s})},1)$, where $\mathbf{s}) \in \mathcal{D}$, and $z(\mathbf{s}) \sim Discrete(\pi_1(\mathbf{s}), \pi_2(\mathbf{s}), \dots , \pi_K(\mathbf{s}))$. where $\pi$ are probbailities and $\pi_j(\mathbf{s})$ must be equal to zero if the triangles neighbor of $\mathbf{s}$ do not have color $j$. My data are the $y$ observed at n spatial locations $\mathbf{s}$ and i need to find the $z$ at the same spatial locations. Each triangle contains only an observed spatial locations – niandra82 Nov 20 '20 at 17:23

1 Answers1

2

If you are only interested in the number of different colorings with $k$ colors, this is the same as partitioning a set into $k$ subsets and the answer is the Stirling number of the second kind, see

Abramowitz, Stegun: Handbook of Mathematical Functions. Section 24.1.3

There might also be solutions for a reformulation of your specific problem in this book.

As you seem to be interested in connected colorings, I do not have a solution, but merely an idea: It might be possible to obtain them by removing $k-1$ edges from the minimum spanning tree of the adjacency graph of the triangles (I think, this adjacency graph is the "Voronoi diagram").

cdalitz
  • 2,844
  • 6
  • 13
  • I don't understand your answer. Do you understand mine? – Carl Nov 07 '20 at 05:56
  • OK, now I understand. Least $\sup4^n$ no? – Carl Nov 07 '20 at 06:40
  • $k^n$ would be the number of possible colorings with $k$ colors. I would guess that the number of connected colorings is more of $n^k$ (or ${n \choose k-1}$, to be more specific), because I think (but cannot prove) that it is equivalent to removing $k-1$ edges from a spanning tree. – cdalitz Nov 07 '20 at 08:29
  • OK, but since $\binom{n}{n}=1$, it would help me to define how many edges a circle has. For example, is it a limiting regular polygon from $n=3\to\infty$ edges, with the same number of vertices, or does it have one edge and zero vertices? – Carl Nov 07 '20 at 17:02
  • Put another way, how does one obtain 1 from a triangular periphery of a 1 color triangle using $\binom{n}{k-1}$? What are $n$ and $k$ in that case? For example, as $\binom{1}{2-1}=1$, are you saying $n=1$ and $k=2$? – Carl Nov 07 '20 at 18:00
  • This does not answer the "connectivity" question, and it is unclear how "connectivity" arises. – Carl Nov 07 '20 at 22:26