Separating Translates in the Plane: Combinatorial Bounds and an Algorithm

Autor: Jean-Marc Robert, Hazel Everett, Jurek Czyzowicz
Rok vydání: 1997
Předmět:
Zdroj: International Journal of Computational Geometry & Applications. :551-562
ISSN: 1793-6357
0218-1959
DOI: 10.1142/s021819599700034x
Popis: Given a family of pairwise disjoint convex sets S in the plane, a set [Formula: see text] is separated from a subset X ⊆ S if there exists a line l such that [Formula: see text] lies on one side of l and the sets in X lie on the other side. In this paper, we establish two combinatorial bounds related to the separation problem for families of n pairwise disjoint translates of a convex set in the plane: 1) there exists a line which separates one translate from at least [Formula: see text] translates, for some constant [Formula: see text] that depends only on the shape of the translates and 2) there is a function [Formula: see text], defined only by the shape of [Formula: see text], such that there exists a line with orientation Θ or [Formula: see text] which separates one translate from at least [Formula: see text] translates, for any orientation Θ. We also present an O(n log (n + k) + k) time algorithm for finding a translate which can be separated from the maximum number of translates amongst families of n pairwise disjoint translates of convex k-gons in the plane.
Databáze: OpenAIRE