=ADD=
=reftype=
14
=number=
00-08
=url=
ftp://ftp.risc.uni-linz.ac.at/pub/techreports/2000/00-08.ps.gz
=year=
2000
=month=
03
=author=
Pau; Petru
=title=
Anchored Sweep: A Paradigm
=abstract=
The subject of this thesis is situated in the frame of computational
geometry. We give here a unified exposition of the utilities of 
the {\it anchored sweep}. We focus on applications in problems of
optimal placement.

Derived from the well established {\it line sweep} paradigm, the
anchored sweep is used for spaces that are topologically homeomorphic 
to a circle or a segment -- usually not a straight line. It has a very 
strong intuition behind it, as it consists basically in 
moving an object with a point anchored on the boundary of
another object, and processing all events that occur during
this movement.

In this thesis, the anchored sweep is used to detect special
position of convex objects in two- and three-dimensional spaces,
namely, positions in which these objects contain a maximum
number of points from a given set. These positions can be attained
by applying either a translation or a rigid motion.

Thus, we present solutions for the following problems: Let $P$
be a convex planar polygon or a polyhedron in three-dimensional space,
and let $S$ be a set of points in plane respectively in space.
Find a translation or a rigid motion $\tau$ such that $\tau(P)$ 
contains a maximum number of points in $S$.

A first discretization of the search space is given by the
{\it stable placements}, i.e., special transformation under which
the boundary of the convex object contains a number of points
from the initial set. We relate the stable placements to the
intersection of a number of certain translated copies of $P$. By
intersecting a number of copies of the initial object a polygon is
obtained; it will be used afterwards as the space that will be swept. 

During the anchored sweep, $P$ is kept with one vertex on the 
polygon given by the intersection. As $P$ traverses the perimeter,
the points in $S$ traverse the boundary of $P$. The position
of $P$ with maximum $S$-points inside is stored.

It is shown here that the lower bound for problems of this type
is $\Omega(n\log n)$, where $n$ is the number of vertices of $P$.
=note=
PhD Thesis
=sponsor=
RISC-Linz scholarship
=keywords=
computational geometry, anchored sweep, optimal placement
=end=