Voronoi Diagram with Respect to Criteria on Vision
Information
Short Running Title: Voronoi Diagram on Vision Information
Tetsuo Asano
School of Information Science,
JAIST, Japan
1-1 Asahidai, Nomi,
923-1292, Japant-asano@jaist.ac.jp
Hisao Tamaki
Department of Computer Science,
Meiji University, Japan
Higashimita, Tama-ku, Kawasaki,
214-8571, Japan
tamaki@cs.meiji.ac.jp

Naoki Katoh
Graduate School of Engineering,
Kyoto University, Japan
Kyoto University Katsura, Nishikyo-ku, Kyoto,
615-8540, Japannaoki@archi.kyoto-u.ac.jp
Takeshi Tokuyama
Graduate School of Information Sciences,
Tohoku University
Aramaki Aza-Aoba, Aoba, Sendai,
980-8579 Japan
tokuyama@dais.is.tohoku.ac.jp

Abstract
Voronoi diagram for a set of geometric objects is a partition of the plane (or space in higher
dimensions) into disjoint regions each dominated by some given object under a predetermined
criterion. In this paper we are interested in various measures associated with criteria on goodnessof an input line segment with respect to each point in the plane as the ”point of view”. These
measures basically show how well a segment or information displayed on the segment can beseen from the point. Mathematically, the measures are defined in terms of the shapes of thetriangle determined by the point and the line segment. We study the combinatorial and algorithmic
complexities of those Voronoi diagrams. We also study an associated optimization problem: finda point that maximizes the smallest measure value over the measures with respect to all the given
line segments. We give sufficient conditions for an optimal point to lie on a Voronoi edge andpresent a heuristic optimization algorithm for those measures having this property.

Keywords:
Algorithms, Computational Geometry, measure on triangles, optimization, triangle,
Visual angle, aspect ratio, minimal height, Voronoi diagram.

1 Introduction
Given a set of points in the plane, we can partition the plane into regions in such a way that any point
in a region associated with some given point is closer to the point than to any other point in the set.
The resulting partition of the plane is called a Voronoi diagram for the point set. Replacing the relation”closer to” with some other criteria we could define a number of variations of the diagram (see e.g.
[4, 11]).
In this paper we propose a yet another abstraction of those Voronoi diagrams for a set of nonintersecting line segments possibly forming a polygon. We consider a measure associated with acriterion on how an input segment can be seen from a point in the plane as a point of view. There
are several possible criteria. Naturally, the distances from the segments and the lengths of segments
are important factors. If two segments are of the same length, one may conclude that the nearer one
should be seen better; however, it is not always the case, since if we see a blackboard from the leftmost
seat in the first row of a classroom, we have difficulty to read letters written on the blackboard. Also,
liquid-crystal display of a laptop computer can be only seen from points in a limited region. Basically,
the visual quality of information given on a line segment s seen from a point p depends on the shapep s defined by s and p such thatp s has s as an edge and p as its opposite vertex.
of triangle
We consider µ p s to measure the quality of the visual information on s obtained at p. Each measureµ may be a goodness measure, with larger values meaning better quality, or a badness measure, withlarger values meaning poorer quality. For example, in usual situations, the distance between p and s
is a badness measure, while the visual angle of s at p, defined to be the internal angle of vertex p of
the triangle
p s, is a goodness measure. Note, however, that the same measure may serve as both
goodness and badness measures in different situations.
Suppose we are given a set S  si of line segments and a measure µ . For each point p in theplane, we are concerned with the segment si for which the value µ p si  is the worst of µ p s j  overall s j , since that segment may present a bottleneck in processing the visual information from all thesegments. If µ is a goodness measure, this naturally gives rise to the Voronoi diagram for whichµ p s is regarded as the distance between p and s: the Voronoi region of si consists of those points
p for which µ p si   µ p s j  for each s j S distinct from si . If µ is a badness measure, for thesame reason, we are instead interested in the farthest-point Voronoi diagram, for which the directionof the inequality is flipped. In the following, we call Voronoi diagrams of the first type minimummeasure Voronoi diagrams and those of the second type maximum-measure Voronoi diagrams. When
it is clear from the context whether measure µ is a goodness measure or a badness measure, we omit
the minimum-measure/maximum-measure distinction and simply say the Voronoi diagram associatedwith µ .
The Voronoi diagram associated with a goodness or badness measure is a rich source of information regarding questions with respect to the measure and the point set. In particular, it can be used
to solve a certain type of optimization problems. For a goodness measure µ , we are interested in themax-min optimization: find a point p that maximizes the minimum of µ p si  over all si S. In thevisual information setting, we look for a point from which we best see the worst-seen object. Fora badness measure, we are interested in the min-max optimization defined similarly. We give somesufficient condition on the measure in order for such an optimal point to always lie on some Voronoi
edge.
With a different criterion we can define a similar but different Voronoi diagram. Voronoi edges arecharacterized in a different manner. The purpose of this paper is to find combinatorial and structuralproperties common to all those Voronoi diagrams associated with measures µ defined for a pair ofpoint and line segment. We describe basic properties to be satisfied by the measures to possess thosecommon properties. It is important for practical use. There may be a number of problems falling into







the class which can be solved using our framework of Voronoi diagrams. Although it is impossible toenumerate all possible optimization criteria, it is possible to investigate basic conditions to be satisfied
by those criteria in order to have their corresponding Voronoi diagrams bear the same combinatorialproperties.
An original motivation of this Voronoi diagram comes from applications to mesh improvement
and robotics. Mesh generation/improvement [5, 6, 10, 12, 13] is an important process for many purposes including Finite Element Method. In a simple setting, a given simple polygon is partitioned
into many small triangles after inserting an appropriate number of points in its interior as vertices oftriangular meshes. Several different criteria have been considered to evaluate the quality of such a
triangular mesh. One of them is to maximize the smallest internal angle (or to minimize the largest
internal angle). Since polygon vertices are fixed, the only way to improve the quality of triangularmesh is either to move internal points or to insert new internal points (or even delete existing internal
points). In robotics, we are interested in locating a robot in the amidst of many polygonal obstacles
by computing its relative position to the most outstanding polygon or line segment in a criterion on
visual information.
The Voronoi diagram is also given as the lower (or upper) envelope of terrains, where a terrain
for a line segment si is defined using µ p si  as height at the point p. A general theory on terrains
by Halperin and Sharir [7] yields an upper bound O n2ε  on the complexity of the lower envelopeof those terrains that is Voronoi diagram, where ε is an arbitrarily small positive constant. In otherwords, the Voronoi diagram has O n2ε  Voronoi edges, and vertices. Despite the high complexity inthe worst case, actual complexity seems to be low by our experiments for a number of polygons.
This paper is organized as follows. In Section 2 we define a Voronoi diagram associated with an
abstract measure µ on a triangle. In Section 3 a list of possible measures is given together with algebraic expressions for those measures. In Section 4, we study the complexity of the Voronoi diagrams
under those measures. In Section 5, we study the associated optimization problems. Finally, Section
6 gives some concluding remarks together with some open problems and future works.

2 Voronoi diagrams for various criteria on triangles
In the following definitions, we deal with minimum-measure Voronoi diagrams. The definitions for
maximum measure Voronoi diagrams are obtained by flipping the directions of the inequalities.
Suppose we are given a set S  si of line segments on the plane and a measure µ on R S. A
point p is said to be dominated by a line segment si S if









  S

µ p si   min µ p s j  s j
For each si(1) S, the Voronoi region V si is defined to be the set of points singly dominated by si, i.e., i(2)
V si    p  Ê2 µ p si  µ p s j  for any j Voronoi edges are defined by curves which are dominated by exactly two elements of S. Formally,
the Voronoi edge E si s j  is defined by  Ê2 µ p si   µ p s j  µ p sk for any k  i jE si s j   p





(3)

Two Voronoi edges may meet at one point, that is a Voronoi vertex. It is defined by  Ê2 µ p si  µ p s j   µ p sk   µ p sl  for any l  i j kv si s j sk   pwhich is a set of points dominated by three or more elements of S.

(4)

As in the usual definition of generalized Voronoi diagrams, we require that the Voronoi regionsË
form a tessellation of the entire plane: V si  V S j   0/ for si  s j and si S V si   R2 , where V si denotes the closure of the Voronoi region V si .
For some measures, this requirement is violated by some degenerate configurations of line segments. For example, consider a measure µ p si  defined to be the distance from point p to the line
including line segment si . If two line segments si and s j lie on a line l, µ p si   µ p s j  for any
point p. Thus, if the set S contains such co-linear pair of line segments, the resulting Voronoi regions
may not form a tessellation. We exclude those degenerate configurations from our considerations. In
practice, we may avoid them by small perturbations.
For yet some other measures, however, the above tessellation requirement is more severely violated, in the sense that small perturbations may not resolve the problem. This may happen when, forexample, the measure with respect to a line segment takes a constant value for all points in some region. We will later see an example of well-motivated measures in this category. When those measures
are used, we need some extra care outside of the framework presented in this paper.
For the sake of the analysis of the complexity of the Voronoi diagrams and their constructions, wewill impose the standard assumption that the measure is described by a constant number of algebraic
functions. We give more details in Section 4.
For our application on visual information, it may make more sense to include visibility considerations in the definition of the Voronoi diagram: a point p belongs to the Voronoi region of si if si
is entirely visible from p (without being hidden by other line segments) and µ p si   µ p s j  forevery s j  si that is entirely visible from p. This modification would make the Voronoi diagrams moredifficult to analyze: we need at least to deals with the possibilitye of some points not dominated by any
segment. In this paper, we are mainly concerned with the basic Voronoi diagrams without visibility
considerations.







3 A list of possible measures
We say that measure µ is symmetric if for each triangle pqr we have µ p qr  µ q r p  µ r pq.
For any measure µ , there are symmetric versions µmax and µ min , defined by









µ max p qr  max µ p qr µ q rp µ r pq
andµ min p qr  min µ p qr µ q rp µ r pq 
We first list a few asymmetric measures. All of them can be used as both goodness and badness
measures depending on the situations.
visual angle Define µ1 p si   θ p si  which is defined to be the visual angle of si from p.
height Define µ2 p si  as the distance from p to the line containing si .

 

 

aspect-ratio Define µ3 p si   µ2 p si  si , where si denotes the length of segment si .
These asymmetric measures are natural for visual information applications, while their symmetric versions are more appropriate for mesh optimization applications: µ1min , µ2min , and µ3min are all
goodness measures and µ1max , µ2max , and µ3max are all badness measures. The following are inherently
symmetric badness measures.
circumcircle Define µ4 p si  to be the radius of the circumcircle of a triangle defined by p si .

eccentricity Define µ5 p si  as follows: it is 0 if the center of the circumcircle of a triangle
p si 
lies in the interior of the triangle. Otherwise, it is the distance from the center to the closest edgeof the triangle.
Figure 1 illustrates some of the listed measures: µ1 , µ2min , µ3min , µ4 , and µ5 .

p

p

si
(a) µ1 (p, si )

si

h

p
h

si

p

p

L

h
si

(c) µmin
3 (p, si ) = h/Lmin(d) µ4 (p, si ) = r(b) µ2 (p, si ) = hsi(e) µ5 (p, si ) = h

Figure 1: A list of measures on triangles
Note that the last measure eccentricity may violate the tessellation requirement discussed in Section 2, due to the constant value 0 for p si  forming an acute triangle.

3.1 Corresponding Voronoi diagrams
Figure 2 shows Voronoi diagrams for some of the measures listed above. The last one shown in (f)takes visibility constraints into account, as described in Section 2. The authors implemented a C
program using LEDA [8] to obtain those figures. For simplicity those diagrams are drawn pixel by
pixel instead of drawing Voronoi edges following equations of corresponding planar curves. In the
figures line segments (polygon edges) have different colors (darkness). Regions associated with a line
segment are painted by the colors (darkness) associated with it.
Although eccentricity may violate the tessellation requirement in general, the line segment configuration in the example does not cause this problem.
Figure 3.1 shows another pair of examples. The measure used for the diagrams is the distanceof the point to the line segment. The visibility condition is considered in the right figure (b), but notin the left one (a). This is known as a Voronoi diagram for a set of line segments. Although theline segments appear to form a polygon, they are slightly perturbed so that no endpoints of two line
segments coincide. If two line segments have a common endpoint, there will be a region of points
equidistant to those two line segments, violating the tessellation requirement.

3.2 Algebraic expressions
Below we list explicit algebraic expressions for the measures listed earlier. They are needed in thealgorithms for construction, and for the analysis of the complexity of associated Voronoi diagrams.
visual angle Although the visual angle itself cannot be expressed as an algebraic function, its cosine
value µ1 p si   cos θ p si  can, which is sufficient for our purpose of constructing the Voronoi
diagram and doing optimization. Exactly, we havecos θ p si   pa2   pb2 ab22 pa  pb



(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: Voronoi diagrams for various measures: (a) visual angle (µ1 ) as a goodness measure, (b)minimum height (µ2min ), (c) minimum aspect ratio (µ3min ), (d) circumcircle (µ4 ), (e) eccentricity (µ5 ),and (f) visual angle as a goodness measure, with visibility constraint.

(a)

(b)

Figure 3: Voronoi diagrams for the usual distance measure. Visibility constraint is taken into consideration in the right diagram (b) but not in the left one (a).

 

where a and b are two endpoints of si and pq denotes the length of the segment pq. Assumingp  x y, a  ax ay , and b  bx by , we havecos θ p si  ax 2  yx2

ay 2  xax 2  yxheight Letting A be the area of the triangle
with respect to si is given by:µ2 p si bx 2  y
ay 2

by 2
x

bx 2

ax

bx 2  y

ay

by 2

by 2



p si  and L be the length of si , the height µ2 p si  of p

2AL
ay by x  bx

ax

ax y  ax by2
bx   ay by 2

bx ay





bx ay





aspect-ratio With the same notation as above, we have:µ3 p si µ2 p si L
2AL2
ay by x  bx ax y  ax by
ax bx 2  ay by 2circumcircle It is known that the radius of a triangle pab with area A is given byµ4 p si  pa  pb abx

4Aax 2  y ay 2 x bx 2  y by 2 ax bx 2  ay
2 ay by x  bx ax y  ax by bx ay





by 2



eccentricity Let r be the radius of the circumcircle of a triangle pab. If the center of the circumcircle lies in the interior of the triangle, µ5 p si   0. Otherwise, µ5 p si  is the smallest of the
distances from the center to the segment pa, pb, and si . Thus, µ5 p si  is expressed as a combination of six algebraic functions, three for the distance from the center to the lines containing
the sides of the triangle and three for the distance from the center to the vertices of the triangle.
We omit the exact expression here.

4 Complexity of Voronoi diagrams
The purpose of this section is to study the combinatorial and algorithmic complexities of our Voronoi
diagrams. We first note that the Voronoi region V si  for each si may not be connected. For example,
let us take the visual angle as the measure and consider minimum-measure Voronoi diagrams. Figure 4
shows an example with three line segments in which Voronoi regions are indeed disconnected.
Figure 5 illustrates a configuration for which the complexity of the diagram is quadratic.
To get an upper bound on the complexity of our Voronoi diagrams, we apply the result of Halperin
and Sharir [7] on the complexity of the lower envelope of terrains defined by algebraic functions.
Let fi , 1 i n, be bivariate algebraic function of a constant degree, possibly partially defined.
Assume that, when fi is partially defined, the domain of the function is bounded by an algebraic curveof a constant degree. Then their result says that the complexity of the lower envelope of the terrains
defined by z  fi x y, 1 i n, is O n2ε  for any positive constant ε . It is also known that theenvelope can be computed in O n2ε  time [1] using a divide and conquer strategy.

 

 

V (s1 )V (s3 )s2

V (s2 )s3

s1
V (s2 )V (s3 )
V (s1 )V (s3 )

V (s1 )

Figure 4: A Voronoi diagram for a set S of three line segments (shown by bold lines) under the measureof max-min visual angle. A point belongs to a Voronoi region dominated by a line segment giving thesmallest visual angle.

Figure 5: A visual angle Voronoi diagram for a set S of horizontal and vertical line segments (shownby bold lines) having quadratic number of Voronoi edges and vertices. Dotted lines in the figure areextensions of given line segments. Segment endpoints are shown by dots in the figure.

Our minimum-measure Voronoi diagram is obtained by projecting the lower envelope of the terrains defined by z  gi x y  µ x y si , si S, to the xy-plane. If µ is defined by a single algebraic
function, then we can immediately apply the above results. For more general cases where µ is definedby a combination of a constant number of algebraic functions, we need to guarantee that the domain ofeach constituent function is bounded by an algebraic curve of a constant degree. To do so, it suffices
to assume that µ p si  for fixed si is continuous except on si .

Theorem 1 Let µ be a measure such that, for each fixed line segment s, µ p s is a piecewise algebraic function on p of a constant degree consisting of a constant number of pieces and is continuous
except on s. Assume further that for some set S of n line segments, the pair µ S satisfies the tessellation requirement. Then, the Voronoi diagram of S under µ consists of O n2ε  cells, edges, andvertices, where ε is an arbitrarily small positive constant, and it can be computed in O n2ε  time.
It is straightforward to verify that all the measures listed above (except for visual angle µ1 whichshould be replaced by the cosine version µ1 ) satisfy the assumption of this theorem.

5 OptimizationGiven a goodness measure µ p s and a set of line segments S  si , our Voronoi diagram gives us
a means for computing min µ p si  si S for each p. As discussed in the introduction, we areinterested in finding a point p that maximizes this function. For badness measures, we are interested
in minimizing the max µ p si  si S . In the following, we deal with goodness measures andassociated max-min optimization problems. Badness measures and associated min-max optimization
problems can be similarly dealt with.
We first give simple sufficient conditions for an optimal point to lie on a Voronoi edge. Given ameasure µ and a fixed line segment s, a point p is a peak of µ with respect to s, if it gives a local
optimum of µ p s as a function on p: for any p in the neighborhood of p , µ p s µ p s. It
is clear that if a measure does not have any peak then optimal points of the max-min optimization
problem must lie on Voronoi edges.
We say that measure µ satisfies the single peak value property, if there is some universal constantc such that for every line segment s we have:

1. µ p s

  
  

 c for every point p, and2. every local optimum of µ p s takes the value c.
Theorem 2 Let µ be a goodness measure satisfying the single peak value property and let S be someset of line segments. Then, each optimal point of the associated max-min optimization problem lies on
a Voronoi edge of the Voronoi diagram for S under µ .

Proof: Let p be a local optimum point for some si S. From the definition of the single peak value
property, we have µ p s j  µ p si  for every s j S, which prohibits p from lying in the Voronoi¾
region of si . Therefore, each optimal point must lie on some Voronoi edge.

Let us consider whether the concrete measures listed earlier satisfy the above sufficient conditions.
The visual angle measure µ1 , together with its symmetric versions µ1min and µ1max , satisfies the single
peak value property as both goodness and badness measures. The aspect ratio µ3 as a badness measure,
together with its symmetric version µ3min , satisfies the single peak value property. The height µ2 as agoodness measure, together with its symmetric version µ2min does not have peaks. However, the radiusof circumcircle µ4 as a badness measure does have peaks (local minima) but does not satisfy the single

peak value property. The peak value for si is just the half of the length of the line segment since thecircle with si as its diameter is the smallest circle passing through the two endpoints of si . Thus, twoline segments having different lengths have different peak values. Thus, µ4 does not satisfy the single
peak value property. In fact, in the Voronoi diagram associated with the measure shown in Figure 6 an
optimal point is not located on Voronoi edges.

Figure 6: A Voronoi diagram associated with the circumcircle radius as a badness measure for twoline segments (drawn by bold lines). An optimal point that minimizes the radius of the maximum
circumcircles is depicted by a cross and connected with four endpoints of the two line segments. The
optimal point does not lie on a Voronoi edge.
For those measures satisfying the condition of the theorem, a natural O n2ε  time algorithm tosolve the max-min optimization problem is to examine all Voronoi edges and compute the optimal
point on each of them. Unfortunately, the time bound is rather large and indeed there is an algorithmwith smaller running time. Our optimization problem can be formulated as an LP-type problem [9]and can be solved in almost linear time. Practical comparisons of these algorithms, however, have yet
to be done through experimental methods.
In the rest of this section, we seek a heuristic algorithm that makes use of the Voronoi diagramsand their property that the optimal points are located on Voronoi edges.

Level Region
Given a goodness measure µ , we define a level region by
R t si  p  Ê 2  µ p si  t That is, it consists of all points at which the measure is greater than some given value t. Rt si  issimilarly defined. Figure 7 shows level regions for some measures listed earlier (although there isanother region symmetric with respect to a line segment, only one of them is shown). For the measureµ1 on max-min visual angle, the level region Rθ si  is the interior of a circle on which the circularangle is exactly θ , as shown in Figure 7(a). For the measure µ2 on max-min height, Rh si  above theline segment si is characterized by two lines each passing through an endpoint of the line segment andthe line parallel to si separated by h from si . Thus, the region is an infinite region bounded by two rays

and one line segment (which may be degenerated to a point). The measure µ3 on max-min aspect ratio
has the level region Rα si  bounded by two circular arcs and one line segment parallel to si . The gap
si where si is the length of si . The two circles determining the
between two parallel lines is α
circular arcs have their center on lines perpendicular to si and passing through the two endpoints of si .
The level region for the measure on min-max circumcircle is not convex. It is bounded by two circular
arcs of the same radius and both passing through the two endpoints of si . As is easily seen, wheneverp si  is given by the circle shown ina point p lies on the boundary, the circumcircle of the triangle
the figure.

 

 

α
h
si
(a)

h

si
(b)

si
(c)

α||si ||

si(d)Figure 7: Level regions Rt si  for four different measures: (a) visual angle as a goodness measure,(b) minimum height, (c) minimum aspect-ratio, and (d) circumcircle as a badness measure.
For a line segment si and a real value t  0, the level region Rt si  appears in both sides of theline segment. In Figure 7 we only illustrate one of the two regions since they are symmetric. Everyboundary curve of the level region is described by a polynomial equation of constant degrees in x andy.

Heuristic Algorithm
The following is a heuristic algorithm for our optimization problem, guided by a Voronoi diagram
associated with a given measure. For simplicity, we assume that the set of line segments form a
convex or star-shaped polygon, but the algorithm can be adapted to more general cases.
Pixel Method(1) Given a convex polygon or a star-shaped polygon P, first distribute k points q1 q2    qk in its
interior, where k is some small constant.
(2) Compute the measures at those points.
(3) Take the best value t among them.
(4) For each polygon edge si , compute the level region R t si .
(5) Take their intersection R by plane sweep (typically in O n log n time).
(6) Enumerate all the Voronoi edges intersecting R. Note that if two level regions for si and s j intersect
on the boundary of R, then it means that the Voronoi edge E si s j  intersects the region R. In
this way we can enumerate all the relevant Voronoi edges.
(7) For each such Voronoi edge, find its peak within R. Then, take the best value t among them.

(8) If the region R is small enough, stop the algorithm with the peak value t found. Otherwise, goback to step (4).
Figure 8 show how the feasible regions are computed for sets of points. In the figure, Voronoi
diagrams for the measure on max-min aspect-ratio are superimposed with level regions for polygonedges. The boundaries of those level regions are depicted by bold lines. It is seen that Voronoi edges
appear at vertices of the boundaries. It is also seen that given k points in the interior of a polygon atleast one point lies on the boundary and no point lies in its interior.
Given k points in the interior of a given polygon, we can compute the values e p1     e pk  inO kn time. Then, compute intersection of n level regions for the largest value among e p1     e pk .
The total time complexity depends on how many iterations we need as well as on the time complexity of the plane sweep, which in turn depends on the complexity of the level curves. There is no
analysis on the running time.

Figure 8: Two sets of points (marked by crosses) distributed over a polygon and their associatedfeasible regions computed by the heuristic algorithm.
Figure 9 show a Voronoi diagram for the measure of max-min aspect ratio with colors and without
colors.

Finding a peak on a Voronoi edge
Both in the exact O n2ε  time algorithm and in the heuristic algorithm, we need to compute an optimal point on a single edge as a primitive operation. This is purely a matter of algebraic calculations.
We illustrate this process with an example.
Take the minimum aspect ratio µ3min as our measure µ . We have:µ p si            if pa is the longest side of                 if pb is the longest side ofif ab is the longest side of     
ay by x bx ax y ax by ay bx
x ax 2 y ay 2
ay by x bx ax y ax by ay bx
x bx 2 y by 2
ay by x bx ax y ax by ay bx
bx ax 2 by ay 2

p si 
p si 
p si 

Figure 9: Voronoi diagram for the measure of max-min aspect ratio with colors and without colors.
where p  x y and ax ay  and bx by  are the starting and ending points of si . We also have threedifferent expressions for µ p sj . Thus, there are 9 different forms of equations for µ p si   µ p s j .
Letting cx cy  and dx dy  be two endpoints of s j , one of possible equations is ay byx  bx axy  axby aybx    cy dyx  dx cxy  cxdy cydx
xax 2  y

ay 2

x

cx 2  ycy 2from which we have an equation for the corresponding Voronoi edge. If we partially differentiate theequations for µ p si  and µ p s j  by x and y and putting them equal to 0, then we have 4 different
equations. Solving the system of equations, we have a constant number of points, which are candidates
for peak positions. Finally, we evaluate the measures at those points and find a point among them thatmaximizes the measure. Figure 10 illustrates terrains associated with polygons with optimal points
highlighted.

6 Concluding Remarks
In this paper we have presented a new family of Voronoi diagrams for a set of line segments or apolygon based on various measures on goodness of triangles. We have succeeded in characterizing
their common combinatorial and structural properties. We have also presented a generic scheme forfinding an optimal point with respect to a specified measure using the Voronoi diagram as guide.
Unfortunately, our complexity result of O n2ε  is not encouraging for practical applications, but thisis just an upper bound on the worst case complexity. Since the worst case is not known, especiallyfor the cases where the set of line segments form a convex or star-shaped polygon, it may be possible
to lower the complexity for those cases. More experimental works are required to judge whether thisidea is useful for practical use, which is left for future work.
It is known in [9] that the problem of finding a point in a star-shaped polygon that maximizes theminimum visual angle when the point is connected to all the vertices of the polygon by straight edges
is formulated as an LP-type problem and thus it can be solved by implementing O n basic operationsin the framework. So, it is more efficient than our approach based on the angular Voronoi diagram.

Figure 10: Terrains on the minimum aspect-ratio Voronoi diagrams. Darker pixels have lower heights.
The peak is highlighted.
Although it is hard to describe in limited space, there is an application in which we are required tofind a point that maximizes the smallest visual angle in a star-shaped polygon in some region boundedby some planar curves such as circular arcs. In such cases the diagram is useful and expected to beefficient because we do not need the whole diagram but just a part of it in the restricted area.

Acknowledgment
The part of this research was partially supported by the Ministry of Education, Science, Sports andCulture, Grant-in-Aid for Scientific Research on Priority Areas. Work of T.A. was partially supportedby the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (B).
We also thank K. Ushikubo for his survey and programming. The first author would like to thankFranz Aurenhammer and his group for their discussions.

References[1] P. Agarwal, O. Schwarzkopf, and Micha Sharir, ”The Overlay of Lower Envelopes and its Applications,” Discrete & Computational Geometry, 15, pp.1-13, 1996.
[2] T. Asano, ”Aspect-ratio Voronoi Diagram with Applications,” Proc. International Symposium on
Voronoi Diagram in Science and Engineering, Banff, Canada, pp.217-223, 2006
[3] T. Asano, N. Katoh, H. Tamaki and T. Tokuyama, ”Angular Voronoi Diagram with Applications,”
ibid, pp.32-39, 2006.
[4] F. Aurenhammer, ”Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure,”
ACM Computing Surveys, 23, 3, pp.345-405, 1991.
[5] 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.
[6] L. A. Freitag and P. Plassmann, ”Local optimization-based simplicial mesh untangling and improvement,” Int. J. for Numerical Methods in Engineering, 49, pp.109–125, 2000.

[7] D. Halperin and M. Sharir, ”Almost tight upper bounds for the single cell and zone problems inthree dimensions,” Proc. Symp. on Comput. Geom., pp.11-20, 1994.
[8] ”LEDA: A library for Efficient Data Types and Algorithms,” Algorithmic Solutions Software
GmbH, Germany.
[9] J. Matoušek, M. Sharir, and E. Welzl, ”A Subexponential Bound for Linear Programming,” Algorithmica, 16, pp.498-516, 1996.
[10] S. A.Mitchell and S. A. Vavasis, ”Quality Mesh Generation in Three Dimensions,” Proc. of theEighth Annual Symp. on Computational Geometry, pp212–221, 1992.
[11] A. Okabe, B. Boots, and K. Sugihara, ”Spatial Tessellations, Concepts and Applications ofVoronoi Diagrams,” John Wiley & Sons, New York, 1992.
[12] J. R. Shewchuk, ”Delaunay refinement algorithms for triangular mesh generation,” Comput.
Geom., Theory and Appl., 22, 1-3, pp.21-74, 2002.
[13] K. Shimada and D. C. Gossard, ”Bubble mesh: automated triangular meshing of non-manifold
geometry by sphere packing,” Proc. of the Third Symposium on Solid Modeling and Applications, pp.409-419, 1995.