Offset-Polygon Annulus Placement Problems
Gill Barequet
Amy J. Briggs
Matthew T. Dickerson
Michael T. Goodrich
Abstract
In this paper we address several variants of the polygon annulus
placement problem: given an input polygon P and a set S of points,
find an optimal placement of P that maximizes the number of points in
S that fall in a certain annulus region defined by P and some offset
distance delta > 0. We address the following variants of the problem:
placement of a convex polygon as well as a simple polygon; placement
by translation only, or by a translation and a rotation; off-line and
on-line versions of the corresponding decision problems; and decision
as well as optimization versions of the problems. We present
efficient algorithms in each case.
A gzip'ed postscript version of this paper
is available.
Back to Amy Briggs' home page