An official website of the United States government
We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of different-size circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density δ∗ is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (δ∗ = 0.5), of circles in a square (δ∗ = 0.5390 . . .), regular octagons in a square (δ∗ = 0.5685 . . .), and circles in a circle (δ∗ = 0.5). 2012 ACM Subject Classification Theory of computation → Packing and covering problems; Theory of computation → Computational geometry
more »
« less
Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)
We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5).
more »
« less
- PAR ID:
- 10163104
- Date Published:
- Journal Name:
- 35th International Symposium on Computational Geometry (SoCG 2019)
- Issue:
- 129
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract When cylinders are packed and wrapped by the bands around the surface, the effective elastic behavior in the cross section of the assembly, which is of significance to its stability and integrity, can be controlled by the wrapping force in the band. The wrapping force is transferred to the cylinders through the Hertz contact between each pair of neighboring cylinders, which is validated by the experiments. The Singum model is introduced to study the mechanical behaviors of the packed cylinders with two-dimensional (2D) packing lattices, in which an inner cylinder is simulated by a continuum particle of Singum and the inter-cylinder force is governed by the Hertz contact model so as to derive the effective stress-strain relationship. The wrapping force will produce configurational forces given a displacement variation, which significantly changes the effective stiffness of the packed cylinders. The hexagonal packing exhibits isotropic elasticity whereas the square packing is anisotropic. The efficacy of our model is demonstrated by comparing the closed form elasticity against the numerical simulation and the previous models. The explicit form of elasticity can be used for packing design and quality control of cable construction and installation.more » « less
-
null (Ed.)Abstract This paper reports a study on the effects of particle size distribution (tuned by mixing different-sized powders) on density of a densely packed powder, powder bed density, and sintered density in binder jetting additive manufacturing. An analytical model was used first to study the mixture packing density. Analytical results showed that multimodal (bimodal or trimodal) mixtures could achieve a higher packing density than their component powders and there existed an optimal mixing fraction to achieve the maximum mixture packing density. Both a lower component particle size ratio (fine to coarse) and a larger component packing density ratio (fine to coarse) led to a larger maximum mixture packing density. A threshold existed for the component packing density ratio, below which the mixing method was not effective for density improvement. Its relationship to the component particle size ratio was calculated and plotted. In addition, the dependence of the optimal mixing fraction and maximum mixture packing density on the component particle size ratio and component packing density ratio was calculated and plotted. These plots can be used as theoretical tools to select parameters for the mixing method. Experimental results of tap density were consistent with the above-mentioned analytical predictions. Also, experimental measurements showed that powders with multimodal particle size distributions achieved a higher tap density, powder bed density, and sintered density in most cases.more » « less
-
Extracellular vesicles (EVs) are membrane-bound nanoparticles (50–1000 nm) secreted by all cell types and play critical roles in various biological processes. Among these, exosomes, a smaller subset of EVs, have attracted considerable interest due to their potential applications in diagnostics and therapeutics. However, conventional EV isolation methods are often limited by inefficiencies in processing time, recovery, and scalability. Hydrophobic interaction chromatography utilizing capillary-channeled polymer (C–CP) fiber stationary phases offers a promising alternative, enabling rapid (<15 min), cost-effective (~$5 per column) EV isolation with high loading capacities (~1010–10¹² particles) and minimal sample pre-processing. Despite these advantages, achieving high-throughput EV isolation for larger-scale applications using the C–CP fiber platform is the present challenge. To this end, further optimization of stationary phase packing and adsorption conditions is necessary to maximize the available binding surface area in the current microbore column format. This study systematically investigates the influence of interstitial fraction (i.e. packing density) in polyester (PET) C–CP fiber columns on the dynamic binding capacity (DBC) of EVs isolated from human urine using a high-performance liquid chromatography platform. Microbore columns (0.76 mm i.d. × 300 mm) packed with PET C–CP fibers in both an eight-channel (PET-8) and a novel trilobal (PET-Y) configuration were evaluated using breakthrough curves and frontal analysis. The results reveal that lower packing densities correlate with higher mass- and surface areabased EV binding capacities, with a maximum DBCs of 2.86 × 10¹³ EVs g-1 fiber and 1.22 × 10¹⁴ EVs m⁻² fiber achieved in <2 min of sample loading. Under optimum conditions, surface utilization of >50 % is realized. These results establish a framework for optimizing C–CP fiber-based platforms to enhance EV capture efficiency, facilitating the development of scalable EV isolation techniques for biomedical research and therapeutic applications.more » « less
-
Given a set $$P$$ of $$n$$ points in the plane, we consider the problem of computing the number of points of $$P$$ in a query unit disk (i.e., all query disks have the same radius). We show that the main techniques for simplex range searching in the plane can be adapted to this problem. For example, by adapting Matoušek's results, we can build a data structure of $O(n)$ space in $$O(n^{1+\delta})$$ time (for any $$\delta>0$$) so that each query can be answered in $$O(\sqrt{n})$$ time; alternatively, we can build a data structure of $$O(n^2/\log^2 n)$$ space with $$O(n^{1+\delta})$$ preprocessing time (for any $$\delta>0$$) and $$O(\log n)$$ query time. Our techniques lead to improvements for several other classical problems in computational geometry. 1. Given a set of $$n$$ unit disks and a set of $$n$$ points in the plane, the batched unit-disk range counting problem is to compute for each disk the number of points in it. Previous work [Katz and Sharir, 1997] solved the problem in $$O(n^{4/3}\log n)$$ time. We give a new algorithm of $$O(n^{4/3})$$ time, which is optimal as it matches an $$\Omega(n^{4/3})$$-time lower bound. For small $$\chi$$, where $$\chi$$ is the number of pairs of unit disks that intersect, we further improve the algorithm to $$O(n^{2/3}\chi^{1/3}+n^{1+\delta})$$ time, for any $$\delta>0$$. 2. The above result immediately leads to an $$O(n^{4/3})$$ time optimal algorithm for counting the intersecting pairs of circles for a set of $$n$$ unit circles in the plane. The previous best algorithms solve the problem in $$O(n^{4/3}\log n)$$ deterministic time [Katz and Sharir, 1997] or in $$O(n^{4/3}\log^{2/3} n)$$ expected time by a randomized algorithm [Agarwal, Pellegrini, and Sharir, 1993]. 3. Given a set $$P$$ of $$n$$ points in the plane and an integer $$k$$, the distance selection problem is to find the $$k$$-th smallest distance among all pairwise distances of $$P$$. The problem can be solved in $$O(n^{4/3}\log^2 n)$$ deterministic time [Katz and Sharir, 1997] or in $$O(n\log n+n^{2/3}k^{1/3}\log^{5/3}n)$$ expected time by a randomized algorithm [Chan, 2001]. Our new randomized algorithm runs in $$O(n\log n +n^{2/3}k^{1/3}\log n)$$ expected time. 4. Given a set $$P$$ of $$n$$ points in the plane, the discrete $$2$$-center problem is to compute two smallest congruent disks whose centers are in $$P$$ and whose union covers $$P$$. An $$O(n^{4/3}\log^5 n)$$-time algorithm was known [Agarwal, Sharir, and Welzl, 1998]. Our techniques yield a deterministic algorithm of $$O(n^{4/3}\log^{10/3} n\cdot (\log\log n)^{O(1)})$$ time and a randomized algorithm of $$O(n^{4/3}\log^3 n\cdot (\log\log n)^{1/3})$$ expected time.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.4230/LIPIcs.SoCG.2019.63
