Double-saturated packing of unit disks

A set of closed unit disks in the Euclidean plane is said to be double-saturated packing if no two disks have inner points in common and any closed unit disk intersects at least two disks of the set. We prove that the density of a double saturated packing of unit disks is ≥ and the lower bound is attained by the family of disks inscribed into the faces of the regular triangular tiling. Partially supported by the Hungarian National Foundation for Scientific Research, grant number 1238.     

Trees that are sphere-of-influence graphs

Given a collection of points in the plane, an open (closed) disk is drawn about each point with radius equal to the smallest distance from that point to any other in the collection. The sphere-of-influence graph (closed-sphere-of-influence graph) is the intersection graph of these disks. Any graph isomorphic to such a graph is a SIG (CSIG). We characterize trees that are SIGs and CSIGs, and obtain a bound on the number of edges in triangle-free SIGs and CSIGs.     

Area-preserving isotopies of self-transverse immersions of S 1 in ℝ2

Let C and C′ be two smooth self-transverse immersions of S ¹ into ?². Both C and C′ subdivide the plane into a number of disks and one unbounded component. An isotopy of the plane which takes C to C′ induces a one-to-one correspondence between the disks of C and C′. An obvious necessary condition for there to exist an area-preserving isotopy of the plane taking C to C′ is that there exists an isotopy for which the area of every disk of C equals that of the corresponding disk of C′. In this paper we show that this is also a sufficient condition.     

On Nehari disks and the inner radius

Let D be a simply connected plane domain and B the unit disk. The inner radius of D, , is defined by . Here S _f is the Schwarzian derivative of f, the hyperbolic density on D and . Domains for which the value of is known include disks, angular sectors and regular polygons, as well as certain classes of rectangles and equiangular hexagons. All of the mentioned domains except non-convex angular sectors have an interesting property in common, namely that , where h maps B conformally onto D. Because of the importance of this property for computing , we say that D is a Nehari disk if holds.?This paper is devoted to the problem of characterizing Nehari disks. We give a necessary and sufficient condition for a domain to be a Nehari disk provided it is a regulated domain with convex corners. Received: March 7, 1996; revised version: July 15, 1999     

Disk allocation methods for binary Cartesian product files

Since a file is usually stored on a disk, the response time to a query is dominated by the disk access time. In order to reduce the disk access time, a file can be stored on several independently accessible disks. In this paper, we discuss the problem of allocating buckets in a file among disks such that the maximum disk accessing concurrency can be achieved. We are particularly concerned with the disk allocation problem for binary Cartesian product files. A new allocation method is first proposed for the cases when the number (m) of available disks is a power of 2. Then it is extended to fit the cases wherem is not a power of 2. The proposed algorithm has a near strict optimal performance for a partial match query in which the number of unspecified attributes is greater than a small number (5 or 6).This work was supported in part by NSF Grant DCR-8405498.     

Two-player Tower of Hanoi

The Tower of Hanoi game is a classical puzzle in recreational mathematics (Lucas 1883) which also has a strong record in pure mathematics. In a borderland between these two areas we find the characterization of the minimal number of moves, which is \(2^n-1\), to transfer a tower of n disks. But there are also other variations to the game, involving for example real number weights on the moves of the disks. This gives rise to a similar type of problem, but where the final score seeks to be optimized. We study extensions of the one-player setting to two players, invoking classical winning conditions in combinatorial game theory such as the player who moves last wins, or the highest score wins. Here we solve both these winning conditions on three pegs.     

Curved Hexagonal Packings of Equal Disks in a Circle

For each k ≥ 1 and corresponding hexagonal number h(k) = 3k(k+1)+1, we introduce packings of h(k) equal disks inside a circle which we call the curved hexagonal packings. The curved hexagonal packing of 7 disks (k = 1, m(1)=1) is well known and one of the 19 disks (k = 2, m(2)=1) has been previously conjectured to be optimal. New curved hexagonal packings of 37, 61, and 91 disks (k = 3, 4, and 5, m(3)=1, m(4)=3, and m(5)=12) were the densest we obtained on a computer using a so-called ``billiards' simulation algorithm. A curved hexagonal packing pattern is invariant under a rotation. For , the density (covering fraction) of curved hexagonal packings tends to . The limit is smaller than the density of the known optimum disk packing in the infinite plane. We found disk configurations that are denser than curved hexagonal packings for 127, 169, and 217 disks (k = 6, 7, and 8). In addition to new packings for h(k) disks, we present the new packings we found for h(k)+1 and h(k)-1 disks for k up to 5, i.e., for 36, 38, 60, 62, 90, and 92 disks. The additional packings show the ``tightness' of the curved hexagonal pattern for k ≤ 5: deleting a disk does not change the optimum packing and its quality significantly, but adding a disk causes a substantial rearrangement in the optimum packing and substantially decreases the quality. Received May 15, 1995, and in revised form March 5, 1996.     

Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.     

The Forest Hiding Problem

Let Ω be a disk of radius R in the plane. A set F of unit disks contained in Ω forms a maximal packing if the unit disks are pairwise interior-disjoint and the set is maximal, i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F, that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n ^5/2log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.     

The Spectra of Small Oscillations of Thin Disk Galactic Models

This paper gives a survey of the spectral properties of the frequencies of small oscillations, both in and perpendicular to their plane, of cold thin disk galactic models. The spectra can have discrete and continuous parts, with two quite distinct types of continua arising. One type occurs with both kinds of oscillation when the density at the outer edge of the disk becomes sufficiently rarified. It is associated with rapid fluctuations in the outer region. The other type of continuum occurs for non-axisymmetric oscillations in the plane of non-uniformly rotating disks. Some significant discrete oscillations of fundamental type are found that exist in addition to the various continua.     

A PTAS for the disk cover problem of geometric objects

We present PTASs for the disk cover problem: given geometric objects and a finite set of disk centers, minimize the total cost for covering those objects with disks under a polynomial cost function on the disks’ radii. We describe the first FPTAS for covering a line segment when the disk centers form a discrete set, and a PTAS for when a set of geometric objects, described by polynomial algebraic inequalities, must be covered. The latter result holds for any dimension.     

Patterns and Structures in Disk Packings

Using a computational procedure that imitates tightening of an assembly of billiard balls, we have generated a number of packings of n equal and non-equal disks in regions of various shapes. Our experiments are of three major types. In the first type, the values of n are in thousands, the initial disk configuration is random and a priori one expects the generated packings to be random. In fact, the packings turn out to display non-random geometric patterns and regular features, including polycrystalline textures with "rattlers" typically trapped along the grain boundaries. An experiment of the second type begins with a known or conjectured optimal disk packing configuration, which is then "frustrated" by a small perturbation such as variation of the boundary shape or a relative increase of the size of a selected disk with respect to the sizes of the other disks. We present such frustrated packings for both large n (~ 10, 000) and small n (~ 50 to 200). Motivated by applications in material science and physics, the first and second type of experiments are performed for boundary shapes rarely discussed in the literature on dense packings: torus, a strip cut from a cylinder, a regular hexagon with periodic boundaries. Experiments of the third type involve the shapes popular among mathematicians: circles, squares, and equilateral triangles the boundaries of which are hard reflecting walls. The values of n in these experiments vary from several tens to few hundreds. Here the obtained configurations could be considered as candidates for the densest packings, rather than random ones. Some of these conjecturally optimal packings look regular and the regularity often extends across different values of n. Specifically, as n takes on an increasing sequence of values, n = n(1), n(2), ...n(k), ..., the packings follow a well-defined pattern. This phenomenon is especially striking for packings in equilateral triangles, where (as far as we can tell from our finite computational experiments), not only are there an infinite number of different patterns, each with its own different sequence n(1), n(2), ...n(k), ..., but many of these sequences seem to continue indefinitely. For other shapes, notably squares and circles, the patterns either cease to be optimal or even cease to exist (as packings of non-overlapping disks) above some threshold value n(k0) (depending on the pattern). In these cases, we try to identify the values of n(k0).     

On the perimeters of simple polygons contained in a disk

A simple n-gon is a polygon with n edges with each vertex belonging to exactly two edges and every other point belonging to at most one edge. Brass et?al. (Research Problems in Discrete Geometry, 2005) asked the following question: For n ???5 odd, what is the maximum perimeter of a simple n-gon contained in a Euclidean unit disk? In 2009, Audet et?al. (Discrete Comput Geom 41:208?C215) answered this question, and showed that the optimal configuration is an isosceles triangle with a multiple edge, inscribed in the disk. In this note we give a shorter and simpler proof of their result, which we generalize also for hyperbolic disks, and for spherical disks of sufficiently small radii.     

An Invariant Measure and the Probability of a Fall in the Problem of an Inhomogeneous Disk Rolling on a Plane

This paper addresses the problem of an inhomogeneous disk rolling on a horizontal plane. This problem is considered within the framework of a nonholonomic model in which there is no slipping and no spinning at the point of contact (the projection of the angular velocity of the disk onto the normal to the plane is zero). The configuration space of the system of interest contains singular submanifolds which correspond to the fall of the disk and in which the equations of motion have a singularity. Using the theory of normal hyperbolic manifolds, it is proved that the measure of trajectories leading to the fall of the disk is zero.     

Diffraction of a plane wave by a circular disk

In this paper we solve the problem of diffraction of a normally incident plane wave by a circular disk. We treat both the hard and soft disk. In each case we obtain the solution as a series which converges when the product of the wave number and the radius of the disk is large. Our construction leads directly to asymptotic approximations to the solution for large wave number.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Failed disk recovery in double erasure RAID arrays

Reliability is a major concern in the design of large disk arrays. In this paper, we examine the effect of encountering more failures than that for which the RAID array was initially designed. Erasure codes are incorporated to enable system recovery from a specified number of disk erasures, and strive beyond that threshold to recover the system as frequently, and as thoroughly, as is possible. Erasure codes for tolerating two disk failures are examined. For these double erasure codes, we establish a correspondence between system operation and acyclicity of its graph model. For the most compact double erasure code, the full 2-code, this underlies an efficient algorithm for the computation of system operation probability (all disks operating or recoverable).When the system has failed, some disks are nonetheless recoverable. We extend the graph model to determine the probability that d disks have failed, a of which are recoverable by solving one linear equation, b of which are further recoverable by solving systems of linear equations, and d−a−b of which cannot be recovered. These statistics are efficiently calculated for the full 2-code by developing a three variable ordinary generating function whose coefficients give the specified values. Finally, examples are given to illustrate the probability that an individual disk can be recovered, even when the system is in a failed state.     

Bending analysis of a functionally graded rotating disk based on the first order shear deformation theory

The theoretical formulation for bending analysis of functionally graded (FG) rotating disks based on first order shear deformation theory (FSDT) is presented. The material properties of the disk are assumed to be graded in the radial direction by a power law distribution of volume fractions of the constituents. New set of equilibrium equations with small deflections are developed. A semi-analytical solution for displacement field is given under three types of boundary conditions applied for solid and annular disks. Results are verified with known results reported in the literature. Also, mechanical responses are compared between homogeneous and FG disks. It is found that the stress couple resultants in a FG solid disk are less than the stress resultants in full-ceramic and full-metal disk. It is observed that the vertical displacements for FG mounted disk with free condition at the outer surface do not occur between the vertical displacements of the full-metal and full-ceramic disk. More specifically, the vertical displacement in a FG mounted disk with free condition at the outer surface can even be greater than vertical displacement in a full-metal disk. It can be concluded from this work that the gradation of the constitutive components is a significant parameter that can influence the mechanical responses of FG disks.     

Nonlinear resonant traveling waves in rotating disks

The resonant conditions for traveling waves in rotating disks are derived. The nonlinear resonant spectrum of a rotating disk is computed from the resonant conditions. Such a resonant spectrum is useful for the disk drive industry to determine the range of operational rotation speed. The resonant wave motions for linear and nonlinear, rotating disks are simulated numerically for a 3.5-inch diameter computer memory disk.