Narrow Results

In this paper we discuss the packing properties of invariant disks defined by periodic behavior of a model for a bandpass Σ–Δ modulator. The periodically coded regions form a packing of the forward invariant phase space by invariant disks. For this one-parameter family of PWIs, by introducing codings underlying the map operations we give explicit expressions for the centers of the disks by analytic functions of the parameters, and then show that tangencies between disks in the packings are very rare; more precisely they occur on parameter values that are at most countably infinite. We indicate how similar results can be obtained for other plane maps that are piecewise isometries.

Given a set of unit disks in the plane with union area A, what fraction of A can be covered by selecting a pairwise disjoint subset of the disks? Rado conjectured 1/4 and proved 1/4.41. Motivated by the problem of channel assignment for wireless access points, in which use of 3 channels is a standard practice, we consider a variant where the selected subset of disks must be 3-colourable with disks of the same colour pairwise-disjoint. For this variant of the problem, we conjecture that it is always possible to cover at least 1/1.41 of the union area and prove 1/2.09. We also provide an O(n²) algorithm to select a subset achieving a 1/2.77 bound. Finally, we discuss some results for other numbers of colours.

This paper considers a problem of locating the given number of disks into a container so that the area covered by the disks is maximized. In the problem, the radii of the disks can be changed arbitrarily unless they overlap outside of the container, and the disks are allowed to overlap with each other. We present an approximation algorithm for this problem assuming that the container is a convex polygon. Our algorithm achieves approximation ratio (0.78 - ϵ) for any small ϵ > 0. Since the computation time of our algorithm depends on the number of corners of the convex polygon exponentially, we also give a heuristic to reduce the number of corners.

For any given $k\in \mathbb{N}$, this paper gives upper bounds on the radius of a packing of a complete hyperbolic surface of finite area by $k$ equal-radius disks in terms of the surface’s topology. We show that these bounds are sharp in some cases and not sharp in others.