To illustrate a raster/image processing solution, I began with the posted image. It is of much lower quality than the original data, due to the superposition of blue dots, gray lines, colored regions, and text; and the thickening of the original red lines. As such it presents a challenge: nevertheless, we can still obtain Voronoi cells with high accuracy.
I extracted the visible parts of the red linear features by subtracting the green from the red channel and then dilating and eroding the brightest parts by three pixels. This was used as the base for a Euclidean distance calculation:
i = Import["http://i.stack.imgur.com/y8xlS.png"];
{r, g, b} = ColorSeparate[i];
string = With[{n = 3}, Erosion[Dilation[Binarize[ImageSubtract[r, g]], n], n]];
ReliefPlot[Reverse@ImageData@DistanceTransform[ColorNegate[string]]]
(All code shown here is Mathematica 8.)
Identifying the evident "ridges"--which must include all points that separate two adjacent Voronoi cells--and re-combining them with the line layer provides most of what we need to proceed:
ridges = Binarize[ColorNegate[
LaplacianGaussianFilter[DistanceTransform[ColorNegate[string]], 2] // ImageAdjust], .65];
ColorCombine[{ridges, string}]
The red band represents what I could save of the line and the cyan band shows the ridges in the distance transform. (There is still a lot of junk due to the breaks in the original line itself.) These ridges need to be cleaned and closed up through a further dilation--two pixels will do--and then we can identify the connected regions determined by the original lines and the ridges between them (some of which need explicitly to be recombined):
Dilation[MorphologicalComponents[
ColorNegate[ImageAdd[ridges, Dilation[string, 2]]]] /. {2 -> 5, 8 -> 0, 4 -> 3} // Colorize, 2]
What this has accomplished, in effect, is to identify five oriented linear features. We can see three separate linear features emanating from a point of confluence. Each has two sides. I have considered the right side of the two rightmost features as being the same, but have otherwise distinguished everything else, giving the five features. The colored areas show the Voronoi diagram from these five features.
A Euclidean Allocation command based on a layer that distinguishes the three linear features (which I did not have available for this illustration) would not distinguish the different sides of each linear feature, and so it would combine the green and orange regions flanking the leftmost line; it would split the rightmost teal feature into two; and it would combine those split pieces with the corresponding beige and magenta features on their other sides.
Evidently, this raster approach has the power to construct Voronoi tessellations of arbitrary features--points, linear pieces, and even polygons, regardless of their shapes--and it can distinguish sides of linear features.
Thiessen polygons are Voronoi diagrams - there is a 'voronoi' package available in the CRAN archives (not the main repository), but the 'deldir' package does the same job.
require(deldir)
# Create some points
x <- c(32.5, 32.1, 33.5, 32.2, 33.0)
y <- c(-2.2, -3.3, -2.3, -2.9, -3.0)
# Calculate the Delaunay triangulation, then the tiles.
z <- deldir(x,y,rw=c(32.0,33.6,-3.4,-2.1))
w <- tile.list(z)
# Make a list of pretty colours, and use 'em to plot:
wcols <- topo.colors(5)
plot(w, fillcol=wcols, close=TRUE)
Now, the 'w' object is a 'tile list', not an sp object, but the tiles could be turned into a spatial object pretty easily, using the x / y components of the list:
> str(w[1])
List of 1
$ :List of 5
..$ ptNum: int 1
..$ pt : Named num [1:2] 32.5 -2.2
.. ..- attr(*, "names")= chr [1:2] "x" "y"
..$ x : num [1:5] 33 32 32 32.6 33
..$ y : num [1:5] -2.1 -2.1 -2.4 -2.67 -2.46
..$ bp : logi [1:5] TRUE TRUE TRUE FALSE FALSE
Best Answer
Several comments have good suggestions to check for duplicate points stacked atop each other and points with no or bad geometry. However the statement in the question that the tool worked partially cued me to take a look at the help file where I noticed the following:
Based on that I questioned which coordinate system you were working in. In your investigations it appears you found that your points weren't projected at all which would probably lead to similar behavior. Apparently getting the points into a proper projection solved the issue with the tool.
I do want to point out a couple of things regarding projections in ArcGIS, just for clarification: