Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userColoring translates and homothets of a convex body
223
0
0.0
(
0
)
Added by
Minghui Jiang
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in $RR^n$.
rate research
Read More
For smooth convex disks $A$, i.e., convex compact subsets of the plane with non-empty interior, we classify the classes $G^{text{hom}}(A)$ and $G^{text{sim}}(A)$ of intersection graphs that can be obtained from homothets and similarities of $A$, respectively. Namely, we prove that $G^{text{hom}}(A)=G^{text{hom}}(B)$ if and only if $A$ and $B$ are affine equivalent, and $G^{text{sim}}(A)=G^{text{sim}}(B)$ if and only if $A$ and $B$ are similar.
Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that live on a cone, in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is visible to a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support a new type of source unfolding of the entire surface of P to one non-overlapping piece, as reported in a companion paper.
We formulate a novel characterization of a family of invertible maps between two-dimensional domains. Our work follows two classic results: The Rado-Kneser-Choquet (RKC) theorem, which establishes the invertibility of harmonic maps into a convex planer domain; and Tuttes embedding theorem for planar graphs - RKCs discrete counterpart - which proves the invertibility of piecewise linear maps of triangulated domains satisfying a discrete-harmonic principle, into a convex planar polygon. In both theorems, the convexity of the target domain is essential for ensuring invertibility. We extend these characterizations, in both the continuous and discrete cases, by replacing convexity with a less restrictive condition. In the continuous case, Alessandrini and Nesi provide a characterization of invertible harmonic maps into non-convex domains with a smooth boundary by adding additional conditions on orientation preservation along the boundary. We extend their results by defining a condition on the normal derivatives along the boundary, which we call the cone condition; this condition is tractable and geometrically intuitive, encoding a weak notion of local invertibility. The cone condition enables us to extend Alessandrini and Nesi to the case of harmonic maps into non-convex domains with a piecewise-smooth boundary. In the discrete case, we use an analog of the cone condition to characterize invertible discrete-harmonic piecewise-linear maps of triangulations. This gives an analog of our continuous results and characterizes invertible discrete-harmonic maps in terms of the orientation of triangles incident on the boundary.
The paper is devoted to coverings by translative homothets and illuminations of convex bodies. For a given positive number $alpha$ and a convex body $B$, $g_{alpha}(B)$ is the infimum of $alpha$-powers of finitely many homothety coefficients less than 1 such that there is a covering of $B$ by translative homothets with these coefficients. $h_{alpha}(B)$ is the minimal number of directions such that the boundary of $B$ can be illuminated by this number of directions except for a subset whose Hausdorff dimension is less than $alpha$. In this paper, we prove that $g_{alpha}(B)leq h_{alpha}(B)$, find upper and lower bounds for both numbers, and discuss several general conjectures. In particular, we show that $h_{alpha} (B) > 2^{d-alpha}$ for almost all $alpha$ and $d$ when $B$ is the $d$-dimensional cube, thus disproving the conjecture from Research Problems in Discrete Geometry by Brass, Moser, and Pach.
Given any two convex polyhedra P and Q, we prove as one of our main results that the surface of P can be reshaped to a homothet of Q by a finite sequence of tailoring steps. Each tailoring excises a digon surrounding a single vertex and sutures the digon closed. One phrasing of this result is that, if Q can be sculpted from P by a series of slices with planes, then Q can be tailored from P. And there is a sense in which tailoring is finer than sculpting in that P may be tailored to polyhedra that are not achievable by sculpting P. It is an easy corollary that, if S is the surface of any convex body, then any convex polyhedron P may be tailored to approximate a homothet of S as closely as desired. So P can be whittled to e.g., a sphere S. Another main result achieves the same reshaping, but by excising more complicated shapes we call crests, still each enclosing one vertex. Reversing either digon-tailoring or crest-tailoring leads to proofs that any Q inside P can be enlarged to P by cutting Q and inserting and sealing surface patches. One surprising corollary of these results is that, for Q a subset of P, we can cut-up Q into pieces and paste them non-overlapping onto an isometric subset of P. This can be viewed as a form of unfolding Q onto P. All our proofs are constructive, and lead to polynomial-time algorithms.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
