Upper bounds for the piercing number of families of pairwise intersecting convex polygons

preprint2012arXivOpen access

Abstract

A convex polygon AA is related to a convex mm-gon K=⋂i=1mki+K= \bigcap_{i=1}^m k_i^+, where k1+,...,km+k_1^+,..., k_m^+ are the mm halfplanes whose intersection is equal to KK, if AA is the intersection of halfplanes a1+,...,ala_1^+,...,a_l, each of which is a translate of one of the ki+k_i^+-s. The planar family A{\cal A} is related to KK if each A∈AA \in {\cal A} is related to KK. We prove that any family of pairwise intersecting convex sets related to a given nn-gon has a finite piercing number which depends on nn. In the general case we show O(3n3)O(3^{n^3}), while for a certain class of families, we decrease the bound to 4(n−2)4(n-2), and for n=3,4n=3,4 the bound is 3 and 6 respectively.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.