# BoundedDiagram Error

Although BoundedDiagram function worked well for a small data set, I got errors in a specific case that I cannot explain. I am sorry I am pasting here a large list but you could not verify it otherwise:

Needs["ComputationalGeometry"];

data2D = {{0., 0.1846}, {-0.1846, 0.}, {0., -0.1846}, {0.1846, 0.}, {0.4189,0.2418},
{0.2418, 0.4189}, {0., 0.4837}, {-0.2418, 0.4189}, {-0.4189, 0.2418},
{-0.4837, 0.},{-0.4189, -0.2418}, {-0.2418, -0.4189}, {0., -0.4837},
{0.2418, -0.4189}, {0.4189, -0.2418}, {0.4837, 0.}, {0.8455, 0.},
{0.8041, 0.2613}, {0.684, 0.497}, {0.497, 0.684}, {0.2613, 0.8041},
{0., 0.8455}, {-0.2613, 0.8041}, {-0.497, 0.684}, {-0.684, 0.497},
{-0.8041, 0.2613}, {-0.8455, 0.}, {-0.8041, -0.2613}, {-0.684, -0.497},
{-0.497, -0.684}, {-0.2613, -0.8041}, {0., -0.8455}, {0.2613, -0.8041},
{0.497, -0.684}, {0.684, -0.497}, {0.8041, -0.2613}, {1.2923, 0.},
{1.2599, 0.2876}, {1.1643, 0.5607}, {1.0103, 0.8057}, {0.8057, 1.0103},
{0.5607, 1.1643}, {0.2876, 1.2599}, {0., 1.2923}, {-0.2876, 1.2599},
{-0.5607, 1.1643}, {-0.8057, 1.0103}, {-1.0103, 0.8057}, {-1.1643, 0.5607},
{-1.2599, 0.2876}, {-1.2923, 0.}, {-1.2599, -0.2876}, {-1.1643, -0.5607},
{-1.0103, -0.8057}, {-0.8057, -1.0103}, {-0.5607, -1.1643}, {-0.2876, -1.2599},
{0., -1.2923}, {0.2876, -1.2599}, {0.5607, -1.1643}, {0.8057, -1.0103},
{1.0103, -0.8057}, {1.1643, -0.5607}, {1.2599, -0.2876}};


You can see in

ListPlot[data2D, AspectRatio -> 1, PlotStyle -> PointSize[Large]]


and in

DiagramPlot[data2D]


that the Voronoi Areas appear clear.

But when using

BoundedDiagram[{{-4, -4}, {4, -4}, {4, 4}, {-4, 4}}, data2D]


I get errors like :

Solve::svars: Equations may not give solutions for all "solve" variables.

BoundedDiagram::nobd: Bounded diagram failed.

If I limit the data set I get correct results (but not always):

BoundedDiagram[{{-4, -4}, {4, -4}, {4, 4}, {-4, 4}}, data2D[[1 ;; 10]]]


Notice that VoronoiDiagram[data2D] produces the correct Voronoi data.

Can anybody explain why this is happening or is it a Mathematica bug ?

Solution

Following Belisarius' advice, I am rolling my own algorithm. Actually I used VoronoiDiagram function (why invent the wheel?). I used a circular bound (of radius 1.5) that seems more appropriate for my application.

v = VoronoiDiagram[data2D];

Module[{start = ray[[1]], end = ray[[2]], sx, sy, ex, ey, l},
{sx, sy} = start; {ex, ey} = end;
l =
(sx*ex + sy*ey + Sqrt[(sx*ex + sy*ey)^2 - (ex^2 + ey^2) (sx^2 + sy^2 - radius^2)])/
(ex^2 + ey^2);
start + l*(end - start)];

{vorvert, vorval} =
{Table[
v[[1, i]]],
{i, 1, Length[v[[1]]]}],
v[[2]]};

DiagramPlot[data2D, vorvert, vorval]


I welcome any improvement - addition.

-
I am thinking about generalizing for arbitrary boundary shape. This is a challenge! – tchronis Nov 21 '13 at 21:24

The problem is that the high symmetry of the point set results in an ill-conditioned matrix. You can see it from:

BoundedDiagram[1.5 {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}},  Union@data2D]


RowReduce::luc: Result for RowReduce of badly conditioned matrix {{0.,-3.,4.5},{1.11022*10^-16,-1.11022*10^-16,0.}} may contain significant numerical errors. >>

So, let's perturb the points slightly:

noise[x_] := x + RandomReal[{0, 10^-4}, 2]
data2DD = noise /@ data2D;
{diagvert1, diagval1} = BoundedDiagram[1.5 {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}}, Union@data2DD];
DiagramPlot[data2DD, diagvert1, diagval1]


-
Thanks @belisarius , the original data set was rounded using Round[data2D,0.0001] but the symmetry remained. I see a perturbation can produce the Voronoi vertices , edges and areas but they are still an approximation. In problems where accuracy matters a lot someone cannot afford a close solution. Also are you sure perturbating will always work ? I am taking N-integrals in the Voronoi areas to calculate SER (Symbol Error Rate) in telecommunication systems for very low Noise - so perturbation interferes greatly in my solutions. Thus i cannot adapt the above tweak. – tchronis Nov 21 '13 at 19:34
@tchronis then I think you'll have to roll your own algorithm paying particular attention to numerical details. – Dr. belisarius Nov 21 '13 at 19:40
@tchronis But if the figure isn't going to change you could pick the polygons by hand once ... just a silly idea. – Dr. belisarius Nov 21 '13 at 19:44
Picking by hand is not my favorite :-) – tchronis Nov 22 '13 at 10:42
@tchronis Perhaps you misunderstood me. What I had in mind is the following: 1) Calculate your original bounded diagram 2) If it is ill conditioned, perturb the points and recalculate 3) Keep the polygon edges list , and apply to your original point set 4) Verify that this is a valid bounded diagram for the original point set. You'll find the fourth step is usually unnecessary if the perturbations are small enough (smaller than your Round[]`) – Dr. belisarius Nov 22 '13 at 11:46