# -Neighbours

Given a point set S, two points x and y are* -neighbours* in the set
S if N(x,y,) contains no point of S, other than x or y, in its
interior. There are various kinds of definitions of N(x,y,). One of
them is called *Lune-Based Neighbourhoods*.
##

Lune-Based Neighbourhoods

Lune-based neighbourhoods N(x,y,) for various >0
### For 1

We difine N(x,y,) to be the intersection of the two circles of
radius d(x,y)/2 centered at the points (1- /2)x+(/2)y and
(/2)x + (1- /2)y, respectively.

When **=**1, N(x,y,) corresponds exactly to
the Gabriel neighbourhood
of x and y. When **=**2, we get the ``relative neighbourhood'' of the RNG.
As approaches , the neighbourhood of x and y approximates the
infinite strip formed by translating the line segment (x, y) normal to itself.

### For [0,1]

We difine N(x,y,) to be the intersection of the two circles of radius
d(x,y)/(2) passing through both x and y. When **=**1, this is
consistent with the definition abvove. As approaches 0, N(x,y,)
approximates the line segment joining x and y. Thus, except in degenerate
situations (three or more points colinear), all point pairs are
-neighbours under this scheme for sufficiently small.

REFERENCES

G.T. Toussaint, Ed., * Computational Geometry,* North-Holland,1985, pp.217-249

go back to Beta Skeleton

go back to Home

*Xiaoming ZHONG*

zxm@cs.mcgill.ca

Sat Mar 22 23:34:51 EST 1997