Aspect-Ratio Voronoi Diagram with Applications
Tetsuo Asano
School of Information Science,
JAIST (Japan Advanced Institute of Science and Technology), Japan
1-1 Asahidai, Nomi, Ishikawa, 923-1292, Japant-asano@jaist.ac.jp.
Abstract
This paper considers a problem of finding an optimal
point within a polygon P in the sense that when we connect
the point to every vertex of P by straight line then the worst
aspect ratio among all resulting triangles is optimized. This
problem has an important application to triangular mesh
improvement. We propose three different approaches toward this problem. The first one is based on some newVoronoi diagram defined by an aspect ratio, which is interesting in itself. The second approach is essentially a binary search defined by geometric intersection. The third
one is grid-based heuristic, which might be practically best
but has no theoretical guarantee on its performance.

1 Introduction
Voronoi diagrams have been applied in many different
areas and different purposes[1, 6]. In this paper we define
a new Voronoi diagram for a set of line segments in theplane, which is called an aspect-ratio Voronoi diagram. This
Voronoi diagram is characterized as follows: given a setof line segments s1 , . . . , sn and a point p in the plane, we
can define a triangle Tr(p, si ) for each line segment si bydrawing lines from p to two endpoints of si . Now, we define
an aspect ratio asp(p, si ) of the triangle Tr(p, si ) by the ratioof the longest side over the shortest side. In our criterion thesmaller the ratio the better the quality of the triangle. Givena set of line segments in the plane, the plane is divided into
so-called Voronoi regions each associated with one of theline segments. A point belongs to a Voronoi region V (si )for the line segment si if si gives the worst (largest) aspectratio among given line segments. Such a Voronoi diagram
is well defined and it is quite interesting it itself.
Once we construct such an aspect-ratio Voronoi diagram
for a set of line segments, using the diagram we can find apoint p∗ that minimizes (optimizes) the largest (worst) aspect ratio. This is not the only way to find such an optimal

point. We could have a more direct algorithm. Fix someconstant λ ≥ 1. Then, for each line segment si we can determine a region of points at which the aspect ratio is at mostλ . If there is non-empty intersection of all those regions,then a point in the intersection achieves a better aspect ratio. This suggests a numerical binary search on the best
possible aspect ratio. Unfortunately, the binary search is
not done in strongly polynomial time. It is also not so easy
to compute the intersection precisely because the boundaryof the above-mentioned regions are characterized by plane
curves consisting of six different circular arcs. Thus, wehave to decide which should be more emphasized numericalpreciseness or reasonable running time with some approximation.
This Voronoi diagram has interesting properties, which
are quite different from ordinary ones. First of all it looks
quite different from ordinary Voronoi diagrams for points.
In our case Voronoi edges consist of plane curves of degree3 polynomial in x and y. A Voronoi region associated witha line segment is not always connected. It may be divided
into a number of connected regions or cells. This fact leads
to high complexity of the diagram.
So far we have mentioned two approaches for finding
an optimal point to minimize the worst aspect ratio for aset of line segments, one based on an aspect-ratio Voronoi
diagram and the other using numerical binary search. Unfortunately, either approach has some disadvantages. If we
adopted the numerical binary search, we would have tocompute intersection of n polygons with circular arcs. If
we used our Voronoi diagram instead, we would have tofind intersection of degree-3 curves. So none of them mayyield a practically easy solution. Thus, we come up with athird approach for practical application. Although we haveno theoretical analysis or bound on its time complexity, it
is easy to implement and fast enough for our application tomesh improvement.

2 Problem Definition
In this paper we consider a problem related to mesh improvement [2, 3, 5, 7, 8] That is, given a triangular meshof a polygon with a number of internal points, we want toimprove the quality of the mesh by appropriately moving
internal points, while fixing all other points, since adding a
new internal point usually brings no advantage to improving the worst aspect ratio. Among many different criteria
for evaluating triangular mesh, we define our aspect ratio
for a triangle by the ratio of the longest side over the shortest side. In this paper we consider a problem of moving one
internal point to optimize triangles incident to it, that is, tominimize the highest aspect ratio of triangles incident to thepoint.
Given a triangular mesh and one internal point p, we firstremove all the triangles incident to p, which results in astar-shaped polygon P. Then, we look for a point p∗ tointerconnect to every vertex of the polygon P that optimizes
the worst aspect ratio of those triangles in P.
In a more general setting, we could take a set of line segments which do not necessarily form a star-shaped polygon.
They could be disjoint, but no proper intersection amongline segments is allowed. Then, we want to find a point
to optimize the worst aspect ratio. But, in this setting, if
we connect the optimal point to all endpoints of the given
line segments, the resulting triangles may have proper intersections. To prohibit intersection among those triangles,
we must limit our search space to a region of points fromwhich all the line segments are visible. If the set of line
segments forms a star-shaped polygon, such a region must
exist and it is called a kernel. If it forms a convex polygon,
the whole interior part of the polygon is the kernel. So, in
this paper we only consider a set of line segments forminga star-shaped polygon and search for a point in its kernel tooptimize the worst aspect ratio.
Now, the goal in this paper is to solve the following problem:
Problem Given a star-shaped polygon P = (s0 , s1 , . . . , sn =s0 ) in the plane, find a point p that optimizes the worst
value among asp(p, s0 ), asp(p, s1 ), . . . , asp(p, sn−1 ), whereasp(p, si ) is an aspect ratio of the triangle defined by the
point p and the line segment si .

3 Basic properties concerning aspect ratio
Given a line segment s = p1 p2 and a point p in the plane,
the aspect ratio asp(p, s) of the triangle defined by connecting the two endpoints of s to p is defined by the ratio of thelongest side over the shortest side of the triangle, i.e.,
asp(p, s) =max{|pp1 |, |pp2 |, |p1 p2 |}.
min{|pp1 |, |pp2 |, |p1 p2 |}(1)

By the definition, an aspect ratio is at least 1 for any triangle
and a triangle of an aspect ratio 1 is a regular triangle ofthree equal sides.
Given a line segment s = p1 p2 in the plane, the plane ispartitioned into regions by circles defined by the two endpoints and their perpendicular bisector, as shown in Figure 1. More precisely, we define two circles C1 and C2 .
The circle C1 is centered at p1 and passes through p2 . C2
has its center at p2 and p1 on it. The perpendicular bisector of the two points p1 and p2 partitions the plane into two
halfplanes. The one containing p1 is denoted by H(p1 , p2 )and the other by H(p2 , p1 ).
The two circles and the bisecting line creates 6 different
regions. They are coded as Ri jk when |si | ≤ |s j | ≤ |sk | forthree sides si , s j and sk of a triangle. Here, s0 = s, s1 = pp1
and s2 = pp2 . The following is a list of those 6 regions with
their associated aspect ratio.
R012 : C1 ∩C2 ∩ H(p1 , p2 ). asp(p, s) = d(p, p2 )/|s|, where|s| is the length of s.
R021 : C1 ∩C2 ∩ H(p2 , p1 ). asp(p, s) = d(p, p1 )/|s|.
R102 : C1 ∩C2 ∩ H(p1 , p2 ). asp(p, s) = d(p, p2 )/d(p, p2 ).
R201 : C1 ∩C2 ∩ H(p2 , p1 ). asp(p, s) = d(p, p1 )/d(p, p2).
R120 : C1 ∩C2 ∩ H(p1 , p2 ). asp(p, s) = |s|/d(p, p1 ).
R210 : C1 ∩C2 ∩ H(p2 , p1 ). asp(p, s) = |s|/d(p, p2 ).
In the following, by R012 (p1 , p2 ) we denote a region R012
for a line segment s = p1 p2 .
R012

R021
p
s1

R102

s2
p2

p1 s = s0

R201

R120 R210
C1

C2
C2

C1
H(p1, p2)

H(p2, p1)

Figure 1. Partition of the plane with respect
to an aspect ratio for a line segment in theplane.
Two intersections of the two circles and the bisector are
special points that achieve asp(p, s) = 1. Intuitively, as apoint goes away from the points, its corresponding aspectratio gets worse. Figure 2 shows contour lines of the same

aspect ratio. The lower figure is a closer look at the same
picture. In those figures, if the worst aspect ratio at a point
is in some interval then it is painted in a color associatedwith the interval. Now define a region R≥λ (s) for a line
segment s = p1 p2 . A point p = (x, y) belongs to the regionR≥λ (s) if and only if asp(p, s) ≥ λ . Such a region exists forany value λ ≥ 1. As is seen in the figures, such a region is
not always connected. As a special case, R≥1 (s) consists of
two points which are the two points achieving asp(p, s) = 1
in both sides of s. As λ increases, the region R≥λ (s) also
grows, forming two connected regions. When λ reaches 2,
the two regions are merged into one connected region with
two holes around the two endpoints of the line segment s.
When λ gets further larger, the two holes get shrunk toward
the endpoints while the external boundary formed by two
big circles centered at two endpoints grow toward infinity.
As is seen in the figures, the boundary of each such region (or contour line) consists of at most 6 circular arcs. In
fact, a contour line giving the same aspect ratio is a circular
arc in each region listed above. For example, if a point p =(x, y) lies in R012 , a contour line
p for asp(p, s = p1 p2 ) = λ ischaracterized by an equation (x − x2 )2 + (y − y2 )2 /d12 =λ , where (x2 , y2 ) is the coordinate of an endpoint p2 and d12
is the length of the line segment s = p1 p2 . Since d12 and λare constants,, if p lies in R102 ,p it defines a circle. Similarlyp
we have (x − x2 )2 + (y − y2 )2 / (x − x1 )2 + (y − y1 )2 =λ , which is again an equation of a circle if it is defined since
λ is a constant.
Figure 3 illustrates how the plane is subdivided by thoseregions associated with two line segments. Consider the intersection between R210 (p1 , p2 ) and R120 (p3 , p4 ) as shownin the figure. Take any point p = (x, y) in the intersection.
The point gives the same aspect ratio to these two line segments if and only if the following equation has a solution:d(p, p2 ) d(p, p3 )
=
,
d12
d34

(2)

where d12 and d34 are the lengths of the segments p1 p2 andp3 p4 , respectively, which are constants. With p2 = (x2 , y2 )and p3 = (x3 , y3 ), we havep(x − x2 )2 + (y − y2 )2
=
d12

p

(x − x3 )2 + (y − y3 )2
,
d34

(3)

which represents a circle if the constant part is positive andd12 6= d34 , and a line if it is positive and d12 = d34 . In adegenerate case where d12 = d34 it represents a line since
the quadratic terms disappear.
On the other hand, any point in the intersection
R201 (p1 , p2 ) ∩ R102 (p3 , p4 ) yields an equationpp(x − x2 )2 + (y − y2 )2(x − x1 )2 + (y − y1 )2p=p(x − x3 )2 + (y − y3 )2(x − x4 )2 + (y − y4 )2,(4)

Figure 2. Contour lines defined by aspect ratios with different scales. Colors correspondto some interval of aspect ratios. For low
aspect ratio, the corresponding region consists of two separate regions, each definedby six circular arcs. For high aspect ratio ≥ 1,
the region is merged into one with two holes
around two endpoints of the given line segment.

which is a curve of degree 3 since the terms x4 , x2 y2 and y4
disappear. In a degenerate case where x2 − x1 = x4 − x3 andy2 − y1 = y4 − y3 hold, it becomes a degree-2 curve, that isa hyperbola. By a careful analysis we have the following
conclusions.
Lemma 1 For two nonintersecting line segments in theplane, a trace of points giving the same aspect ratio forthem is either a circular arc or a degree-3 curve (a line ora hyperbola in degenerate cases, respectively).

R210 (p1 , p2 ) ∩ R120 (p3 , p4 )

p4

p3
p1

Figure 4. Subdivision of the plane by aspect ratios, which are defined by two circles
and one bisecting line for each line segment.
Each point is painted in a color assigned to aline segment which gives a larger aspect ratio.

p2

This also implies that a Voronoi region V (si ) for si is definedbyFigure 3. Subdivision of the plane by regions
associated with two line segments by four
circles and two bisecting lines determined by
the two line segments.

Figure 4 illustrates how the entire plane is partitioned
into regions. Two different colors are assigned to two line
segments. When one of them gives worse (larger) aspect ratio for a point, the point is painted in a color assigned to theline segment. The boundary between different regions are
circular arcs or plane curves of degree 3 (if no degeneracy)characterized by Eq.(4).

4 Aspect-ratio Voronoi diagram
Now we are ready to define an aspect-ratio Voronoi diagram for a given set S of line segments s1 , s2 , . . . , sn in theplane. We define an aspect-ratio Voronoi diagram in sucha way that a point p belongs to a Voronoi region associated with a line segment si if and only if si gives the worst(largest) aspect ratio, that is,
asp(p, si ) ≥ asp(p, s j ) for any j 6= i.

(5)

V (si ) = {p ∈ R2 |asp(p, si ) ≥ asp(p, s j ) for any j 6= i}.
(6)Each Voronoi region is bounded by curves at which twoline segments give the same aspect ratio, which are either
circular arcs or degree-3 curves defined earlier (lines andhyperbolas if any degenracy). Endpoints or intersectionof those curves (referred to as primitive curves, hereafter)
are Voronoi vertices and those primitive curves joining two
such vertices are Voronoi edges. A minimal region bounded
by Voronoi edges is called a Voronoi cell. Every Voronoi
cell is associated with a line segment, but the reverse is notalways true. That is, a Voronoi region for a line segment
may be divided into many Voronoi cells.
The partition of the plane into Voronoi cells is called an
aspect-ratio Voronoi diagram for the set of line segments.
Two such Voronoi diagrams are shown in Figure 5, one fora triangle and the other for a convex polygon. In each case
Voronoi regions are distinguished by colors each defined fora line segment. The lower Voronoi diagram contains disconnected Voronoi regions.
Now, let us analyze the combinatorial complexity of ourVoronoi diagram for n line segments. First recall that an
aspect ratio asp(p) at a point p is defined as the largest valueamong aspect ratios for all line segments, that is,
asp(p) = max{asp(p, s1 ), asp(p, s2 ), . . . , asp(p, sn )}. (7)Since asp(p, si ) is defined at any point p, if we regard thevalue as the height at the point, the function asp(p, si ) is aterrain. We have n terrains and an aspect ratio asp(p) at apoint p is given by the largest value among them. Thus, ouraspect-ratio Voronoi diagram is an upper envelope of thosen terrains. The result by Halperin and Sharir [4] gives abound O(n2+ε ) for any small positive constant ε. Thus, thecomplexity of our aspect-ratio Voronoi diagram is O(n2+ε ).
Fortunately, we can improve the bound to O(n2 ) in the following theorem.
Theorem 2 An aspect-ratio Voronoi diagram for a set of nlines in the plane consists of O(n2 ) Voronoi vertices, edges,
and cells.
Proof: As stated above, an aspect ratio is given as an upperenvelope of n terrains. We further decompose each terrain.
Recall that an aspect ratio for a point p and a line segments = (p1 , p2 ) is defined by the ratio of the longest side overthe shortest side. In other words, it is the maximum amongsix ratios between two sides of a triangle Tr(p, s). Therefore, we haved(p, p1 ) d(p, p2 )
|s|
|s|
,
,
,
,
|s|
|s|
d(p, p1 ) d(p, p2 )d(p, p2 ) d(p, p1 ),},d(p, p1 ) d(p, p2 )asp(p, s) = max{

Figure 5. Two aspect-ratio Voronoi diagrams.
In general, the shortest side has the largest
Voronoi region.

where |s| is the length of s and d(p, q) is the distance between two points p and q. If we consider the above six
terms separately, two of them are convex cylinders with thebottom at endpoints of s, other two of them are concave
cylinders with the top again at endpoints of s, and the theremaining two are not cylinders but concave with infinite
height at endpoints of s. So, we have 2n convex terrains and4n concave terrains and the upper envelope of those terrains
gives us an aspect-ratio Voronoi diagram. The complexityof the upper envelope of 4n concave terrains is O(n2 ) andso is that of 2n convex terrains. Thus, the combined upperenvelope also has the complexity O(n2 ).
2Lemma 3 Given an aspect-ratio Voronoi diagram for a setof n line segments in the plane, an optimal point to optimize
the worst aspect ratio is found either on Voronoi edges orat Voronoi vertices. There are only a constant number ofpeaks on each Voronoi edge.
Proof: A Voronoi edge is a primitive curve defined by twoline segments. Due to the shape of contour lines consistingof 6 circular arcs, there are only a constant number of peaks

on the edge. If a point lies in the interior of a Voronoi cell,
we can always find a better point in its neighborhood.
2
Given a set of n line segments in the plane, we can construct an aspect-ratio Voronoi diagram in O(n3 ) time. It
looks quite slow and there may be a more efficient algorithm, but it also looks hopeless to have an algorithm running in subquadratic time in the worst case. In our case ourinterest is only on a part of the Voronoi diagram in the interior of a given star-shaped polygon. It is not known whether
the diagram is simpler in the interior. A number of experimental results indicate linear complexity. So, a naive algorithm may be good enough for practical application (but notheoretical guarantee at present).

hull of those points and limit our search only to the interior of the convex hull. We iterate this search some certain
number of times until the search space becomes sufficiently
small. Then, take the best point as a solution. This is aheuristic algorithm.

7 Another Definition of Aspect Ratio
There is another way of defining an aspect ratio, whichmight be more popular than the one above. A common
equation for an area of a triangle is to multiply the basetimes the one-half the height. If we choose the longest side
as the base, the aspect ratio is defined by the ratio of thelongest side over the corresponding height, that is,

5 Direct approach for finding an optimalpoint
Our goal here was to find a point p∗ with the minimum
asp(p) value. We can find such an optimal point in a more
direct fashion. It is basically a binary search on the optimalvalue asp(p∗ ). Fix a constant λ ≥ 1. Then, for each line
segment we can calculate a region R≥λ of points p such thatasp(p) ≥ λ . When we restrict our search space to the interior of a given star-shaped polygon P, for any constituent
edge si the intersection of R≥λ (si ) with the interior of P always consists of one connected region. If all those regions
have non-empty intersection, that is, ifR≥λ (s0 ) ∩ · · · ∩ R≥λ (sn−1 ) 6= 0/

asp(T ) =greater than λ . Otherwise, that is, if the intersection isempty, it is greater than λ . This enables a binary search. Although the binary search does not give us an algorithm running in strongly polynomial time, parametric search leads
to a strongly polynomial time. Since the detail of an implementation of a parallel algorithm is so complicated due tonon-convexity of a region R≥λ (si ), we just suggest possibility of a polynomial-time algorithm.

6 Practically reasonable algorithm
So far we have proposed two different approaches to findan optimal point to minimize the worst aspect ratio. Unfortunately, however, none of the two algorithms seems tobe practical. In many applications we do not insist on an
exact solution. In such a case we could use a heuristic or
approximation algorithm. One way is to distribute many
points in the kernel of a given star-shaped polygon and thenevaluate those points p by their asp(p) values. Choose the kbest points among them (k should be say something like one
fourth of the number of those points). Construct the convex(9)

Suppose we are given a line segment s between two
points p1 (x1 , y1 ) and p2 (x2 , y2 ). An arbitrary point p(x, y)in the plane defines a triangle Tr(s, p) by connecting p to
the two endpoints of s. Let L be the length of the longest
side of Tr(s, p) and h be the corresponding height. Recall
that the area S of Tr(s, p) is given by2S= |x(y1 − y2 ) + x1 (y2 − y) + x2 (y − y1 )|= |(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |, (10)which is linear in x and y. Since 2S = Lh, we have(8)

then we can conclude that the optimal value asp(p∗ ) is notlongest sidecorresponding heightasp(s, p) =

L L2
= .
h 2S

(11)

Thus, we have three cases:
Case 1: pp1 is the longest side
L2 is given by (x − x1 )2 + (y − y1 )2 , and thus we haveasp(s, p) =(x − x1 )2 + (y − y1 )2. (12)|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |Case 2: pp2 is the longest side
L2 is given by (x − x2 )2 + (y − y2 )2 , and thus we haveasp(s, p) =(x − x2 )2 + (y − y2 )2. (13)|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |Case 3: p1 p2 is the longest side
L2 is given by (x1 −x2 )2 +(y1 −y2 )2 , which is a constant,
say C, and thus we haveasp(s, p) =C
. (14)|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |From the above observations it turns out that a contour
line of the same aspect ratio is a circle in the cases 1 and 2
and a line in the case 3.

(x − x1 )2 + (y − y1 )2|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |===(x − x3 )2 + (y − y3 )2,|(y3 − y4 )x + (x4 − x3 )y + x3 y4 − x4 y3 |(x − x1 )2 + (y − y1 )2|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |C,|(y3 − y4 )x + (x4 − x3 )y + x3 y4 − x4 y3 |C|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |C.
|(y3 − y4 )x + (x4 − x3 )y + x3 y4 − x4 y3 |The first and second equations give degree-3 curves and thethird one gives a line.
2
Figure 6. Contour lines defined by aspect ratios.

Figure 7 shows two Voronoi diagrams using the new aspect ratio.

8 Concluding Remarks
Figure 6 illustrates contour lines of different aspect ratios. As is easily seen, fixed an aspect ratio, points of the
aspect ratio are either on circular arcs or on a straight line
segment. In fact, for any constant λ(x − x1 )2 + (y − y1 )2=λ|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |(15)gives a circle andasp(s, p) =asp(s, p) =C|(y1 − y2 )x + (x2 − x1 )y + x1 y2 − x2 y1 |We have presented three different approaches to find apoint that optimizes the worst aspect ratio of triangles resulting by inserting a point. The first two algorithms run
in polynomial time and find an optimal point, but the last
one does not. Nevertheless, the last one seems to be thebest among three for practical use. So, one important future
work is to establish a theoretical guarantee on the performance of the third algorithm. It is also interesting to improve the performance of the first two algorithms. It is alsointeresting to use a different definition for aspect ratio.

(16)

gives a line.
Using the aspect ratio, we can also define a Voronoi diagram as before. Then, how can we characterize Voronoi
edges? We have seen that Voronoi edges for aspect ratios
defined by longest and shortest sides are given by circular
arcs and degree-3 curves. The circular arcs may be replacedwith lines and the degree-3 curves may be with hyperbolas
if any degeneracy. For the aspect ratio using longest sideand height Voronoi edges are either lines or degree-3 curves
and there are no degenerate cases.

Acknowledgment
The part of this research was partially supported by the
Ministry of Education, Science, Sports and Culture, Grantin-Aid for Scientific Research on Priority Areas. The author would like to thank Kiyoshi Kumahata of JAIST for
his valuable suggestions. The author also would like tothank Oswin Aichholzer, Franz Aurenhammer, and Thomas
Hackl for their discussions.

References

Lemma 4 For two nonintersecting line segments in theplane, a trace of points giving the same aspect ratio for themis either a line or a degree-3 curve.

[1] F. Aurenhammer, ”Voronoi Diagrams – A Survey of a
Fundamental Geometric Data Structure,” ACM Computing Surveys, 23, 3, pp.345-405, 1991.

Proof: Voronoi edges are characterized by equations[2] H. Edelsbrunner and N. Shah, ”Incremental topological flipping works for regular triangulations, ”Proc.

of the 8th ACM Symp. on Computational Geometry
1992, pp.43–52, 1992.
[3] L. A. Freitag and P. Plassmann, ”Local optimizationbased simplicial mesh untangling and improvement,”
Int. J. for Numerical Methods in Engineering, 49,
pp.109–125, 2000.
[4] D. Halperin and M. Sharir, ”Almost tight upperbounds for the single cell and zone problems in three
dimensions,” Proc. Symp. on Comput. Geom., pp.1120, 1994.
[5] S. A.Mitchell and S. A. Vavasis, ”Quality Mesh Generation in Three Dimensions,” Proc. of the Eighth Annual Symp. on Computational Geometry, pp212–221,
1992.
[6] A. Okabe, B. Boots, and K. Sugihara, ”Spatial Tessellations, Concepts and Applications of Voronoi Diagrams,” John Wiley & Sons, New York, 1992.
[7] J. R. Shewchuk, ”Delaunay refinement algorithms fortriangular mesh generation,” Comput. Geom., Theory
and Appl., 22, 1-3, pp.21-74, 2002.
[8] K. Shimada and D. C. Gossard, ”Bubble mesh: automated triangular meshing of non-manifold geometryby sphere packing,” Proc. of the Third Symposium on
Solid Modeling and Applications, pp.409-419, 1995.

Figure 7. Two aspect-ratio Voronoi diagrams.