Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Largest Empty Square Queries in Rectilinear Polygons
verfasst von : Michael Gester, Nicolai Hähnle, Jan Schneider
Erschienen in: Computational Science and Its Applications -- ICCSA 2015
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a rectilinear polygon
P
and a point
$$p \in P$$
p
∈
P
, what is a largest axis-parallel square in
P
that contains
p
? This question arises in VLSI design from physical limitations of manufacturing processes. Related problems with disks instead of squares and point sets instead of polygons have been studied previously.
We present an efficient algorithm to preprocess
P
in time
O
(
n
) for simple polygons or
$$O(n \log n)$$
O
(
n
log
n
)
if holes are allowed. The resulting data structure of size
O
(
n
) can be used to answer largest square queries for any point in
P
in time
$$O(\log n)$$
O
(
log
n
)
. Given a set of points
Q
instead of a rectilinear polygon, the same algorithm can be used to find a largest square containing a given query point but not containing any point in
Q
in its interior.