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: |
Discrete mathematics
Plane (geometry) Applied Mathematics Regular polygon Convex set Function (mathematics) Disjoint sets Theoretical Computer Science Combinatorics Computational Mathematics Computational Theory and Mathematics Orientation (geometry) Line (geometry) Geometry and Topology Algorithm Linear separability Mathematics |
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 |
Externí odkaz: |