**COMPUTATIONAL
GEOMETRY**

**COMP 507, FALL
2003**

**THE UNIMODAL DISTANCE
FUNCTION IN** **COMPUTATIONAL
GEOMETRY**

A function **f: R-> R** is ** unimodal** if it
increases to a maximum(minimum) value, and then decreases(increases).

It is ** strictly unimodal** if it increases and
decreases strictly. Essentially what it means is that once the
function peaks, then on it's way down, it can't decide to go back up
for a bit ever again.

For the purposes of the project, we'll consider polygons unimodal even if the function remains constant over an interval. This makes life easier (well, algorithmically, it doesn't. But we won't go there yet).

The very concept of UNIMODALITY applies to a number of different fields including probability theory, statistics, and of course, what we’re looking at here, computational geometry.

Introduction Distance Functions Relationship Algorithms Properties Applet Open References

Defining the Distance
Function

We will be using the Euclidean Distance for all figures and theorems shown here. It is possible to extend this to other metrics including the Minkowski Metric, the Max-Metric etc, but for computational geometry purposes, it is easier to consider only the Euclidean Metric.

There are 3 cases to deal with:

**1. Vertex - Vertex Distance :**

**2. Vertex - Line Distance :**

**3. Line - Vertex Distance :**

An obvious observation that we make here is that in cases (2) and (3) i.e. VERTEX-LINE and LINE-VERTEX, solving case (2) for all VERTEX-LINE distance pairs is equivalent (computationally) to solving case (3) for all LINE-VERTEX pairs.

In general though, we are interested in only case **(1)-
VERTEX- VERTEX distance.**

Introduction Distance Functions Relationship Algorithms Properties Applet Open References and Links

The Relationship
Between Convexity and Unimodality

In all the analysis, one question looms above all others. The answer has far-reaching impacts on computational complexities, correctness of algorithms, and generalizations of properties of polygons.

What’s the relationship between UNIMODALITY and CONVEXITY?

-In short, NONE.

We provide examples or rather, counterexamples of different cases of polygons which disprove our premises.

**1. Vertex-Vertex **

So i*s a convex polygon unimodal? – NO*

*So, is a unimodal polygon convex? - NO*

The assumption- **CONVEXITY ó
UNIMODALITY is FALSE. This is fundamentally very important, and
the assumption of this falsity led to a number of famous diameter
algorithms for polygons being incorrect. For more on that, visit a
great webpage by another COMP 507 alumnus, Mats Suderman. Go to
Diameter
Algorithms**.

**2. VERTEX-LINE**

*So is a convex polygon unimodal? NO*

The point **a**
here is bimodal with respect to its perpendicular distance from the
edges of the polygon P.

d_{a,Li,i+1}= {0,5,2,5,0}

But here, we give ourselves hope, a polygon that is **f(p _{i}
^ Lj,j+1) unimodal **must be

**Proof:**

Assume P is not convex.

Then P contains at least one reflex vertex.

Let p

_{k}be such a vertex.Take f(L

_{k,k+1}^ p_{i}).We have that Jordan’s Curve theorem => there exist vertices p

_{i }such that d(L_{k,k+1}_{i}) > 0But, d(L

_{k, k+1 }^ ) < 0 since p_{k}is reflex.Also, d(L

_{k,k+1}^ p_{k}) = 0, since p_{k}is a vertex of the edge.Thus, f(L

_{k,k+1}^ p_{i}) is at least bimodal, and hence not unimodal.**This provides us with a contradiction.**

*So finally, to summarize our findings we have the
following relationships.*

**CONVEXITY ó LINE-VERTEX Unimodality****Convexity <= Vertex-Line Unimodality****Convexity ó Vertex-Vertex Unimodality is FALSE**

Introduction Distance Functions Relationship Algorithms Properties Applet Open References and Links

So now we come to the next important part: determining the modality of a convex polygon.

We of course can consider the Brute-Force algorithm that computes distances between every pair of points in the polygon and checks if the Unimodality property holds or not. We use that in our aplet. But, here we present a more elegant algorithm that is particularly useful with large sets of points.

**The following algorithm determines the modality of a convex
polygon in time O(n+m), n = |V| , m =
modality, reference (3).**

It tests whether a convex n-gon is unimodal in q(n) time (proven best possible)

It is also extended to simple polygons – it computes
modality of an n-vertex simple polygon in O(n^{1.695}) time.

Now for the notation required:

s(i) – successor edge to edge 1

OP(i) – edge perpendicularly opposite to edge I

PB(i) – perpendicular bisector of edge I

pv(i) – previous vertex of edge I

sv(i) – successor vertex to edge I

P is m-modal if the sum of the modalities of the vertices equals m.

The modality of vertex pv(i) is the number of extremum vertices in the sequence

pv(s(i)), pv(s^{2}(i)), … , pv(s^{n-1}(i))

sv(j) is an *extremum vertex* with respect to pv(i) if
*either* i or ii hold:

i) d[pv(i), pv(j)] < d[pv(i), sv(j)] > d[pv(i), sv(s(j))]

ii) d[pv(i), pv(j)] > d[pv(i), sv(j)] < d[pv(i), sv(s(j))]

**Algorithm VALGMODAL:**

Array entry V(i) stores the modality of vertex pv(i) for every edge i of the polygon. Initialize V to zero in O(n) time steps.

Compute PB(0) and OP(0) in time O(n). OP(0) is found by scanning at most (n-1) edges to see which one intersects PB(0).

(

*General Step*) To simplify notation, we define edge number k to be the edge s^{k}(0). For 0 <= k <= n-1, compute PB(k) and the intersection of PB(k) with PB(k+1). Note that 2 bisectors must intersect since the polygon is in a given standard form, with no two edges parallel to each other (otherwise the perpendicular bisectors would be parallel too). Determine OP(k+1) by distinguishing between the two cases:

** Case 1: **Intersection
point lies inside the polygon, ie PB(k)intersection PB(k+1) is in
between the midpoint of edge k and PB(k)intOP(k).

Traverse clockwise and check if OP(k),
s(OP(k)),…s^{j}(OP(k)) intersect PB(k+1).

Let s^{j}(OP(k)) intersect
PB(k+1).

Then increment the modality of
vertices: sv(OP(k)), sv(s(OP(k))),…,(sv(s^{j-1}(OP(k)))
not including sv(OP(k)) if it is the intersection point of PB(k) and
OP(k).

** Case 2:** The intersection of PB(k) and PB(k+1) lies
outside the polygon.

* 2.1: *PB(k) intersects edge k+1 between midpoint
of edge k+1 and pv(k+1) .

Traverse clockwise from k+1 to OP(k+1). Increase the modality of all encountered vertices that are

not adjacent to:

sv(k) i.e. sv(k+2),..,pv (OP(k+1)) but not counting this last vertex if OP(k+1) is edge k.

** 2.2: **PB(k+1) intersects edge k between midpoint of edge
k and sv(k). Traverse clockwise

from OP(k) to edge k and increase modality of all vertices not adjacent to:

sv(k),…,sv(OP(k)), pv (k-1) not counting the first vertex if OP(k) = edge k+1 or

if it is the intersection point of OP(k) and PB(k).

** 2.3: **Neither PB(k+1) nor PB(k) intersect edge k or edge
k+1 respectively as shown (figure d).

Traverse CCW and check if PB(k+1) intersects any of OP(k),
pv(OP(k)),….pv^{j}(OP(k))) and let

pvj(OP(k)) be OP(k+1).

Then as in 1, increment modality of: pv(OP(k)),
pv(p(OP(k))),…pv(p^{j-1}(OP(k))) not including the

last vertex if it is the intersection of PB(k+1) and OP(k+1).

Since the last two intersection points of PB(k) are known at the beginning of the k-th iteration , the intersection points of PB(k+1) are calculated in O(1). Also, whether or not PB(k+1) or PB(k) intersect each edge k or k+1 respectively takes O(1).

Thus every iteration of step 3 takes time proportional to the number of vertices whose modality has been incremented.

Thus

**overall time**for all iterations for an m-modal polygon:**O(n+m).**The algorithm can also be generalized to account for degeneracies, and can be expanded to account for all sorts of polygons, not just simple ones.

Introduction Distance Functions Relationship Algorithms Properties Applet Open References

**1.** The Nearest Neighbour of every vertex p_{i} is
an adjacent vertex of p_{i} if P is unimodal.

*The corollary also holds: * If a simple polygon P is
unimodal, then the closest pair of vertices forms an edge in
PG(P).

**2.** Define Global Symmetric Furthest Neighbours and Local
Symmetric Furthest Neighbour:

Then if the simple polygon P is unimodal, then every Local SFN pair of vertices of P is also a Global SFN pair.

**3.** Unimodality is the property that provides the linearity
in the Dobkin-Snyder algorithm.

**4. **Algorithms solving the ALL-FURTHEST-NEIGHBOUR problem do
so in linear time for convex unimodal polygons.

**5. **A convex polygon need not
contain a single vertex whose distance function f(pi, pj) is unimodal
(see Convexity, ...)

Introduction Distance Functions Relationship Algorithms Properties Applet Open References

Applet

Much of the background code for the applet was from S. Legghe's website. Many thanks to him for making it publicly available. It's at: ww.cs.mcgill.ca/~legghe/geo

In order for the relationship to be made clearer between Convexity and Unimodality, the applet allows you to input a convex polygon on the fly and lets you know if it's convex or not.

To the Applet.

Introduction Distance Functions Relationship Algorithms Properties Applet Open References and Links

1. Can the *ALL-FURTHEST-NEIGHBOU*R problem be solved in
linear time for convex polygons?

2. Given a *random convex n-gon*, what is the *probability*
that it is *unimodal*?

Introduction Distance Functions Relationship Algorithms Properties Applet Open References and Links

1. Toussaint, G. T., "*Complexity,
Convexity and Unimodality*" International Journal of Computer
and Information Sciences, vol. 13, No. 3, June 1984, pp.197-217.

Pach, J., “

*On an isoperimetric problem*”, studia Sci Math Hungary, 13:43-45, 1978Aggarwal, Alok, Melville, R., “

*Fast Computation of the Modality of Polygons*”, Journal of Algorithms, 7,(3): 369-381 (1986)

Links:

**The best bar-brewed beer in
Montreal is in this bar.**

Introduction Distance Functions Relationship Algorithms Properties Applet Open References and Links

Contact: saurja.sen@mail.mcgill.ca . For anything.