Packing Ellipsoids with Overlap

The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application---chromosome organization in the human cell nucleus---is discussed briefly, and some illustrative results are presented.

• Publication year

  2012

• Venue

  SIAM Review

• Publication date

  2012-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/120872309arXiv 1204.0235
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Distance between homologous chromosomes results from chromosome positioning constraints

  2010cited by this paper
• Chromosome territories.

  2010cited by this paper
• Stable Morphology, but Dynamic Internal Reorganisation, of Interphase Human Chromosomes in Living Cells

  2010cited by this paper
• Chromosomal rearrangements during human epidermal keratinocyte differentiation

  2009cited by this paper
• A probabilistic model for the arrangement of a subset of human chromosome territories in WI38 Human fibroblasts

  2009cited by this paper
• Cell type specific chromosome territory organization in the interphase nucleus of normal and cancer cells

  2009cited by this paper
• A Survey of the S-Lemma

  2007cited by this paper
• Chromosome territories have a highly nonspherical morphology and nonrandom positioning

  2007cited by this paper
• Three-Dimensional Maps of All Chromosomes in Human Male Fibroblast Nuclei and Prometaphase Rosettes

  2005cited by this paper
• Packing and Covering

  2004cited by this paper
• Improving the Density of Jammed Disordered Packings Using Ellipsoids

  2004cited by this paper
• Convex Analysis and Nonlinear Optimization: Theory and Examples. Jonathan M. Borwein and Adrian S. Lewis, Springer, New York, 2000

  2003cited by this paper
• Evolutionary conservation of chromosome territory arrangements in cell nuclei from higher primates

  2002cited by this paper
• Aspects of semidefinite programming : interior point algorithms and selected applications

  2002cited by this paper
• Convex Analysis And Nonlinear Optimization

  2000cited by this paper
• The Kepler conjecture

  1998cited by this paper
• Linear Matrix Inequalities In System And Control Theory

  1998cited by this paper
• Curved Hexagonal Packings of Equal Disks in a Circle

  1997influential reference
• Linear Matrix Inequalities in Systems and Control Theory

  1994cited by this paper
• Optimization And Nonsmooth Analysis

  1983cited by this paper

• Quasi-Packing Different Spheres with Ratio Conditions in a Spherical Container

  2023cites this paper
• Methodology of Creation of Artificial Core Reservoir Formations Using Geometric Design Methods

  2023cites this paper
• Leaf Shape and Self-Mulching by Trees: A Hypothesis

  2023cites this paper
• Volumetric Representation and Sphere Packing of Indoor Space for Three-Dimensional Room Segmentation

  2021cites this paper
• Simulating Infiltration as a Sequence of Pinning and De-pinning Processes

  2021cites this paper
• A new penalty/stochastic approach to an application of the covering problem: The gamma knife treatment

  2020cites this paper
• Collapse Behavior of Tensegrity Barrel-Vault Structures Based on Di-Pyramid (DP) Units

  2020cites this paper
• Packing ovals in optimized regular polygons

  2019influential citation
• A matheuristic approach with nonlinear subproblems for large-scale packing of ellipsoids

  2019cites this paper
• Optimized ellipse packings in regular polygons

  2019cites this paper
• On Calculating the Packing Efficiency for Embedding Hexagonal and Dodecagonal Sensors in a Circular Container

  2019cites this paper
• A NEW PENALTY/STOCHASTIC APPROACH TO AN APPLICATION OF THE COVERING PROBLEM: THE GAMMA KNIFE TREATMENT

  2019cites this paper
• PACKING OF ELLIPSOIDS IN A CONVEX CONTAINER

  2018cites this paper
• Orientation and repositioning of chromosomes correlate with cell geometry–dependent gene expression

  2017influential citation
• Regulation of genome organization and gene expression by nuclear mechanotransduction

  2017cites this paper
• Ellipsoid Targeting with Overlap

  2017cites this paper
• Chromosome Intermingling: Mechanical Hotspots for Genome Regulation.

  2017cites this paper
• Digital/virtual microstructures in application to metals engineering – A review

  2017cites this paper
• Large-scale packing of ellipsoids ∗

  2017cites this paper
• Clusters of polyhedra in spherical confinement

  2016cites this paper
• Optimal Packing of General Ellipses in a Circle

  2016cites this paper
• Solution to the problem of optimal packing of homothetic ellipsoids in a container of minimum volume

  2016cites this paper
• Large Workspace Robots

  2016cites this paper
• Geometric control and modeling of genome reprogramming

  2016cites this paper
• General Ellipse Packings in an Optimized Circle Using Embedded Lagrange Multipliers

  2016cites this paper
• Packing ellipsoids into volume-minimizing rectangular boxes

  2015cites this paper
• Quasi-Phi-Functions in Packing Problem of Ellipsoids

  2015cites this paper
• Genetic algorithm based optimization technique for underwater sensor network positioning and deployment

  2015cites this paper
• Conceptual Design Aspects of Three General Sub-Classes of Multi-Rotor Configurations: Distributed, Modular, and Heterogeneous

  2015cites this paper
• Packing ellipsoids by nonlinear optimization

  2015cites this paper
• Enumerating Rigid Sphere Packings

  2014cites this paper
• Sphere Packing with Limited Overlap

  2014cites this paper
• Convergence analysis of a heuristic collective sphere packing algorithm

  2014cites this paper
• Uncovering Proximity of Chromosome Territories using Classical Algebraic Statistics

  2014cites this paper
• A Performance Index for Planar Repetitive Workspace Robots

  2014cites this paper
• Deterministic and stochastic global optimization techniques for planar covering with ellipses problems

  2013cites this paper
• Convergence Analysis of a Heuristic Collective Sphere Packing Algorithm

  2013cites this paper
• Métodos estocásticos de otimização global para empacotar círculos em elipses

  2012cites this paper