CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Packing problems - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"7136e8f4-8517-4561-b808-6042d18a0b9c","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Packing_problems","wgTitle":"Packing problems","wgCurRevisionId":1236278829,"wgRevisionId":1236278829,"wgArticleId":213003,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Commons category link from Wikidata","Use dmy dates from September 2019","Packing problems"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Packing_problems","wgRelevantArticleId":213003,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Packing_problem", "wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgInternalRedirectTargetUrl":"/wiki/Packing_problems","wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q3851477","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true, "wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar", "ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/2/26/Seissand.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1421"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/2/26/Seissand.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="947"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="758"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Packing problems - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Packing_problems"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Packing_problems&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Packing_problems"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Packing_problems rootpage-Packing_problems skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Packing+problems" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Packing+problems" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Packing+problems" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Packing+problems" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Packing_in_infinite_space" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Packing_in_infinite_space"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Packing in infinite space</span> </div> </a> <button aria-controls="toc-Packing_in_infinite_space-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Packing in infinite space subsection</span> </button> <ul id="toc-Packing_in_infinite_space-sublist" class="vector-toc-list"> <li id="toc-Hexagonal_packing_of_circles" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hexagonal_packing_of_circles"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.1</span> <span>Hexagonal packing of circles</span> </div> </a> <ul id="toc-Hexagonal_packing_of_circles-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Sphere_packings_in_higher_dimensions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Sphere_packings_in_higher_dimensions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.2</span> <span>Sphere packings in higher dimensions</span> </div> </a> <ul id="toc-Sphere_packings_in_higher_dimensions-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Packings_of_Platonic_solids_in_three_dimensions" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Packings_of_Platonic_solids_in_three_dimensions"> <div class="vector-toc-text"> <span class="vector-toc-numb">1.3</span> <span>Packings of Platonic solids in three dimensions</span> </div> </a> <ul id="toc-Packings_of_Platonic_solids_in_three_dimensions-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Packing_in_3-dimensional_containers" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Packing_in_3-dimensional_containers"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Packing in 3-dimensional containers</span> </div> </a> <button aria-controls="toc-Packing_in_3-dimensional_containers-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Packing in 3-dimensional containers subsection</span> </button> <ul id="toc-Packing_in_3-dimensional_containers-sublist" class="vector-toc-list"> <li id="toc-Different_cuboids_into_a_cuboid" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Different_cuboids_into_a_cuboid"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Different cuboids into a cuboid</span> </div> </a> <ul id="toc-Different_cuboids_into_a_cuboid-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Spheres_into_a_Euclidean_ball" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Spheres_into_a_Euclidean_ball"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Spheres into a Euclidean ball</span> </div> </a> <ul id="toc-Spheres_into_a_Euclidean_ball-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Spheres_in_a_cuboid" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Spheres_in_a_cuboid"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Spheres in a cuboid</span> </div> </a> <ul id="toc-Spheres_in_a_cuboid-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Identical_spheres_in_a_cylinder" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Identical_spheres_in_a_cylinder"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Identical spheres in a cylinder</span> </div> </a> <ul id="toc-Identical_spheres_in_a_cylinder-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Polyhedra_in_spheres" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Polyhedra_in_spheres"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.5</span> <span>Polyhedra in spheres</span> </div> </a> <ul id="toc-Polyhedra_in_spheres-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Packing_in_2-dimensional_containers" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Packing_in_2-dimensional_containers"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Packing in 2-dimensional containers</span> </div> </a> <button aria-controls="toc-Packing_in_2-dimensional_containers-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Packing in 2-dimensional containers subsection</span> </button> <ul id="toc-Packing_in_2-dimensional_containers-sublist" class="vector-toc-list"> <li id="toc-Packing_of_circles" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Packing_of_circles"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Packing of circles</span> </div> </a> <ul id="toc-Packing_of_circles-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Packing_of_squares" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Packing_of_squares"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Packing of squares</span> </div> </a> <ul id="toc-Packing_of_squares-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Packing_of_rectangles" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Packing_of_rectangles"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Packing of rectangles</span> </div> </a> <ul id="toc-Packing_of_rectangles-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Related_fields" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Related_fields"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Related fields</span> </div> </a> <ul id="toc-Related_fields-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Packing_of_irregular_objects" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Packing_of_irregular_objects"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Packing of irregular objects</span> </div> </a> <ul id="toc-Packing_of_irregular_objects-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Notes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Notes"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Notes</span> </div> </a> <ul id="toc-Notes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">9</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Packing problems</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 7 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-7" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">7 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Problema_de_empaquetado" title="Problema de empaquetado – Spanish" lang="es" hreflang="es" data-title="Problema de empaquetado" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-eo mw-list-item"><a href="https://eo.wikipedia.org/wiki/Pakada_problemo" title="Pakada problemo – Esperanto" lang="eo" hreflang="eo" data-title="Pakada problemo" data-language-autonym="Esperanto" data-language-local-name="Esperanto" class="interlanguage-link-target"><span>Esperanto</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%B1%84%EC%9A%B0%EA%B8%B0_%EB%AC%B8%EC%A0%9C" title="채우기 문제 – Korean" lang="ko" hreflang="ko" data-title="채우기 문제" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E5%95%8F%E9%A1%8C" title="パッキング問題 – Japanese" lang="ja" hreflang="ja" data-title="パッキング問題" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-ro mw-list-item"><a href="https://ro.wikipedia.org/wiki/Probleme_de_%C3%AEmpachetare" title="Probleme de împachetare – Romanian" lang="ro" hreflang="ro" data-title="Probleme de împachetare" data-language-autonym="Română" data-language-local-name="Romanian" class="interlanguage-link-target"><span>Română</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D1%83%D0%BF%D0%B0%D0%BA%D0%BE%D0%B2%D0%BA%D0%B8" title="Задачи упаковки – Russian" lang="ru" hreflang="ru" data-title="Задачи упаковки" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BF%D0%B0%D0%BA%D1%83%D0%B2%D0%B0%D0%BD%D0%BD%D1%8F" title="Задача пакування – Ukrainian" lang="uk" hreflang="uk" data-title="Задача пакування" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3851477#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Packing_problems" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Packing_problems" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Packing_problems"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Packing_problems&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Packing_problems&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Packing_problems"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Packing_problems&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Packing_problems&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Packing_problems" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Packing_problems" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Packing_problems&oldid=1236278829" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Packing_problems&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Packing_problems&id=1236278829&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPacking_problems"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FPacking_problems"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Packing_problems&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Packing_problems&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Packing_problems" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q3851477" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=Packing_problem&redirect=no" class="mw-redirect" title="Packing problem">Packing problem</a>)</span></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Problems which attempt to find the most efficient way to pack objects into containers</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about geometric packing problems. For numerical packing problems, see <a href="/wiki/Knapsack_problem" title="Knapsack problem">Knapsack problem</a>.</div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Seissand.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Seissand.png/220px-Seissand.png" decoding="async" width="220" height="261" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/2/26/Seissand.png/330px-Seissand.png 1.5x, //upload.wikimedia.org/wikipedia/commons/2/26/Seissand.png 2x" data-file-width="369" data-file-height="437" /></a><figcaption><a href="/wiki/Sphere" title="Sphere">Spheres</a> or <a href="/wiki/Circle" title="Circle">circles</a> packed loosely (top) and more densely (bottom)</figcaption></figure> <style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1246091330">.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title" style="font-size:130%;"><a href="/wiki/Linear_programming#Covering/packing_dualities" title="Linear programming">Covering/packing-problem pairs</a></th></tr><tr><td class="sidebar-content"> <table style="width:100%;border-collapse:collapse;border-spacing:0px 0px;border:none;display:block;margin-top:0.4em;"><tbody><tr style="vertical-align:top"><td style="font-weight:bold;background:#ddf;text-align:center;border:1px #fafafa solid;"> <a href="/wiki/Covering_problems" title="Covering problems">Covering problems</a></td><td style="font-weight:bold;background:#ddf;text-align:center;border:1px #fafafa solid;"> <a class="mw-selflink selflink">Packing problems</a></td></tr><tr style="vertical-align:top"><td style="padding-top:0.15em;"> <a href="/wiki/Set_cover_problem" title="Set cover problem">Minimum set cover</a></td><td style="padding-top:0.15em;"> <a href="/wiki/Set_packing" title="Set packing">Maximum set packing</a></td></tr><tr style="vertical-align:top"><td> <a href="/wiki/Edge_cover" title="Edge cover">Minimum edge cover</a></td><td> <a href="/wiki/Matching_(graph_theory)" title="Matching (graph theory)">Maximum matching</a></td></tr><tr style="vertical-align:top"><td> <a href="/wiki/Vertex_cover" title="Vertex cover">Minimum vertex cover</a></td><td> <a href="/wiki/Independent_set_(graph_theory)" title="Independent set (graph theory)">Maximum independent set</a></td></tr><tr style="vertical-align:top"><td> <a href="/wiki/Bin_covering_problem" title="Bin covering problem">Bin covering</a></td><td> <a href="/wiki/Bin_packing_problem" title="Bin packing problem">Bin packing</a></td></tr><tr style="vertical-align:top"><td> <a href="/wiki/Polygon_covering" title="Polygon covering">Polygon covering</a></td><td> <a href="/wiki/Rectangle_packing" title="Rectangle packing">Rectangle packing</a></td></tr></tbody></table></td> </tr><tr><td class="sidebar-navbar"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Covering/packing-problem_pairs" title="Template:Covering/packing-problem pairs"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Covering/packing-problem_pairs" title="Template talk:Covering/packing-problem pairs"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Covering/packing-problem_pairs" title="Special:EditPage/Template:Covering/packing-problem pairs"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1126788409">.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}</style><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1246091330"><table class="sidebar sidebar-collapse nomobile nowraplinks plainlist"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="/wiki/Puzzle" title="Puzzle">Puzzles</a></th></tr><tr><td class="sidebar-image" style="padding:0 0 1.0em;"><span class="noviewer" typeof="mw:File"><a href="/wiki/File:Jigsaw.svg" class="mw-file-description" title="Jigsaw piece"><img alt="Jigsaw piece" src="//upload.wikimedia.org/wikipedia/commons/thumb/7/75/Jigsaw.svg/100px-Jigsaw.svg.png" decoding="async" width="100" height="90" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/75/Jigsaw.svg/150px-Jigsaw.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/75/Jigsaw.svg/200px-Jigsaw.svg.png 2x" data-file-width="600" data-file-height="540" /></a></span></td></tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:lavender;text-align:center;;color: var(--color-base)"><span style="font-size:120%">Types</span></div><div class="sidebar-list-content mw-collapsible-content" style="padding-left:1.5em;padding-right:1.5em;"><table class="sidebar nomobile nowraplinks hlist" style="background-color: transparent; color: var( --color-base ); border-collapse:collapse; border-spacing:0px; border:none; width:100%; margin:0px; font-size:100%; clear:none; float:none"><tbody><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Guessing_game" class="mw-redirect" title="Guessing game">Guessing</a></th></tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Riddle" title="Riddle">Riddle</a></li> <li><a href="/wiki/Situation_puzzle" title="Situation puzzle">Situation</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Logic_puzzle" title="Logic puzzle">Logic</a></th></tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Dissection_puzzle" title="Dissection puzzle">Dissection</a></li> <li><a href="/wiki/Induction_puzzles" title="Induction puzzles">Induction</a></li> <li><a href="/wiki/Logic_puzzle#Logic_grid_puzzles" title="Logic puzzle">Logic grid</a></li> <li><a href="/wiki/Self-reference_puzzle" title="Self-reference puzzle">Self-reference</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Mechanical_puzzle" title="Mechanical puzzle">Mechanical</a></th></tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Combination_puzzle" title="Combination puzzle">Combination</a></li> <li><a href="/wiki/Construction_puzzle" title="Construction puzzle">Construction</a></li> <li><a href="/wiki/Disentanglement_puzzle" title="Disentanglement puzzle">Disentanglement</a></li> <li><a href="/wiki/Lock_puzzle" class="mw-redirect" title="Lock puzzle">Lock</a></li> <li><a href="/wiki/Tsumego" title="Tsumego"><i>Go</i> problems</a></li> <li><a href="/wiki/Mechanical_puzzle#Fold_puzzles" title="Mechanical puzzle">Folding</a></li> <li><a href="/wiki/Stick_puzzle" title="Stick puzzle">Stick</a></li> <li><a href="/wiki/Tiling_puzzle" title="Tiling puzzle">Tiling</a></li></ul></td> </tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Tour_puzzle" title="Tour puzzle">Tour</a></li> <li><a href="/wiki/Sliding_puzzle" title="Sliding puzzle">Sliding</a></li> <li><a href="/wiki/Chess_problem" title="Chess problem">Chess</a></li> <li><br /> <a href="/wiki/Maze" title="Maze">Maze</a> (<a href="/wiki/Logic_maze" title="Logic maze">Logic maze</a>)</li></ul></td> </tr><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Word_game" title="Word game">Word</a> and <a href="/wiki/Mathematical_puzzle" title="Mathematical puzzle">Number</a></th></tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/Crossword" title="Crossword">Crossword</a></li> <li><a href="/wiki/Sudoku" title="Sudoku">Sudoku</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Puzzle_video_game" title="Puzzle video game">Puzzle video games</a></th></tr><tr><td class="sidebar-content" style="padding-top:0;padding-bottom:0.5em;"> <ul><li><a href="/wiki/List_of_maze_video_games" title="List of maze video games">Mazes</a></li></ul></td> </tr><tr><th class="sidebar-heading" style="padding-bottom:0;"> <a href="/wiki/Metapuzzle" title="Metapuzzle">Metapuzzles</a></th></tr></tbody></table></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible"><div class="sidebar-list-title" style="background:lavender;text-align:center;;color: var(--color-base)"><span style="font-size:120%"><a href="/wiki/List_of_puzzle_topics" title="List of puzzle topics">Topics</a></span></div><div class="sidebar-list-content mw-collapsible-content" style="padding-left:1.5em;padding-right:1.5em;"><div class="hlist"> <ul><li><a href="/wiki/Brain_teaser" title="Brain teaser">Brain teaser</a></li> <li><a href="/wiki/Dilemma" title="Dilemma">Dilemma</a></li> <li><a href="/wiki/Riddle_joke" title="Riddle joke">Joke</a></li> <li><a href="/wiki/Optical_illusion" title="Optical illusion">Optical illusion</a></li> <li><a class="mw-selflink selflink">Packing problems</a></li> <li><a href="/wiki/Paradox" title="Paradox">Paradox</a></li> <li><a href="/wiki/Problem_solving" title="Problem solving">Problem solving</a></li> <li><a href="/wiki/Puzzlehunt" class="mw-redirect" title="Puzzlehunt">Puzzlehunt</a></li> <li><a href="/wiki/Syllogism" title="Syllogism">Syllogism</a></li> <li><a href="/wiki/Riddle-tale" title="Riddle-tale">Tale</a></li></ul> </div></div></div></td> </tr><tr><td class="sidebar-content"> <div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="background:lavender;text-align:center;;color: var(--color-base)"><span style="font-size:120%">Lists</span></div><div class="sidebar-list-content mw-collapsible-content" style="padding-left:1.5em;padding-right:1.5em;"> <ul><li><a href="/wiki/List_of_impossible_puzzles" title="List of impossible puzzles">Impossible puzzles</a></li> <li><a href="/wiki/List_of_maze_video_games" title="List of maze video games">Maze video games</a></li> <li><a href="/wiki/Nikoli_(publisher)" title="Nikoli (publisher)">Nikoli puzzle types</a></li> <li><a href="/wiki/List_of_puzzle_video_games" title="List of puzzle video games">Puzzle video games</a></li> <li><a href="/wiki/List_of_puzzle_topics" title="List of puzzle topics">Puzzle topics</a></li></ul></div></div></td> </tr><tr><td class="sidebar-navbar"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Puzzles" title="Template:Puzzles"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Puzzles" title="Template talk:Puzzles"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Puzzles" title="Special:EditPage/Template:Puzzles"><abbr title="Edit this template">e</abbr></a></li></ul></div></td></tr></tbody></table> <p><b>Packing problems</b> are a class of <a href="/wiki/Optimization_problem" title="Optimization problem">optimization problems</a> in <a href="/wiki/Mathematics" title="Mathematics">mathematics</a> that involve attempting to pack objects together into containers. The goal is to either pack a single container as <a href="/wiki/Packing_density" title="Packing density">densely</a> as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life <a href="/wiki/Packaging" title="Packaging">packaging</a>, storage and transportation issues. Each packing problem has a dual <a href="/wiki/Covering_problem" class="mw-redirect" title="Covering problem">covering problem</a>, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap. </p><p>In a <a href="/wiki/Bin_packing_problem" title="Bin packing problem">bin packing problem</a>, people are given: </p> <ul><li>A <i>container</i>, usually a two- or three-dimensional <a href="/wiki/Convex_region" class="mw-redirect" title="Convex region">convex region</a>, possibly of infinite size. Multiple containers may be given depending on the problem.</li> <li>A set of <i>objects</i>, some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.</li></ul> <p>Usually the packing must be without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal <a href="/wiki/Packing_density" title="Packing density">packing density</a>. More commonly, the aim is to pack all the objects into as few containers as possible.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Packing_in_infinite_space">Packing in infinite space</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=1" title="Edit section: Packing in infinite space"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Many of these problems, when the container size is increased in all directions, become equivalent to the problem of packing objects as densely as possible in infinite <a href="/wiki/Euclidean_space" title="Euclidean space">Euclidean space</a>. This problem is relevant to a number of scientific disciplines, and has received significant attention. The <a href="/wiki/Kepler_conjecture" title="Kepler conjecture">Kepler conjecture</a> postulated an optimal solution for <a href="/wiki/Sphere_packing" title="Sphere packing">packing spheres</a> hundreds of years before it was <a href="/wiki/Mathematical_proof" title="Mathematical proof">proven</a> correct by <a href="/wiki/Thomas_Callister_Hales" title="Thomas Callister Hales">Thomas Callister Hales</a>. Many other shapes have received attention, including ellipsoids,<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Platonic_solid" title="Platonic solid">Platonic</a> and <a href="/wiki/Archimedean_solid" title="Archimedean solid">Archimedean solids</a><sup id="cite_ref-Torquato_3-0" class="reference"><a href="#cite_note-Torquato-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> including <a href="/wiki/Tetrahedron_packing" title="Tetrahedron packing">tetrahedra</a>,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Tripod_packing" title="Tripod packing">tripods</a> (unions of <a href="/wiki/Cube" title="Cube">cubes</a> along three positive axis-parallel rays),<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> and unequal-sphere dimers.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Hexagonal_packing_of_circles">Hexagonal packing of circles</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=2" title="Edit section: Hexagonal packing of circles"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Circle_packing_(hexagonal).svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Circle_packing_%28hexagonal%29.svg/220px-Circle_packing_%28hexagonal%29.svg.png" decoding="async" width="220" height="220" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Circle_packing_%28hexagonal%29.svg/330px-Circle_packing_%28hexagonal%29.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/69/Circle_packing_%28hexagonal%29.svg/440px-Circle_packing_%28hexagonal%29.svg.png 2x" data-file-width="200" data-file-height="200" /></a><figcaption>The hexagonal packing of circles on a 2-dimensional Euclidean plane.</figcaption></figure> <p>These problems are mathematically distinct from the ideas in the <a href="/wiki/Circle_packing_theorem" title="Circle packing theorem">circle packing theorem</a>. The related <a href="/wiki/Circle_packing" title="Circle packing">circle packing</a> problem deals with packing <a href="/wiki/Circle" title="Circle">circles</a>, possibly of different sizes, on a surface, for instance the <a href="/wiki/Plane_(geometry)" class="mw-redirect" title="Plane (geometry)">plane</a> or a <a href="/wiki/Sphere" title="Sphere">sphere</a>. </p><p>The <a href="/wiki/N-sphere" title="N-sphere">counterparts of a circle</a> in other dimensions can never be packed with complete efficiency in <a href="/wiki/Dimension" title="Dimension">dimensions</a> larger than one (in a one-dimensional universe, the circle analogue is just two points). That is, there will always be unused space if people are only packing circles. The most efficient way of packing circles, <a href="/wiki/Circle_packing" title="Circle packing">hexagonal packing</a>, produces approximately 91% efficiency.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Sphere_packings_in_higher_dimensions">Sphere packings in higher dimensions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=3" title="Edit section: Sphere packings in higher dimensions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Sphere_packing" title="Sphere packing">Sphere packing</a></div> <p>In three dimensions, <a href="/wiki/Close-packing_of_spheres" class="mw-redirect" title="Close-packing of spheres">close-packed</a> structures offer the best <i>lattice</i> packing of spheres, and is believed to be the optimal of all packings. With 'simple' sphere packings in three dimensions ('simple' being carefully defined) there are nine possible definable packings.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> The 8-dimensional <a href="/wiki/E8_lattice" title="E8 lattice">E8 lattice</a> and 24-dimensional <a href="/wiki/Leech_lattice" title="Leech lattice">Leech lattice</a> have also been proven to be optimal in their respective real dimensional space. </p> <div class="mw-heading mw-heading3"><h3 id="Packings_of_Platonic_solids_in_three_dimensions">Packings of Platonic solids in three dimensions</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=4" title="Edit section: Packings of Platonic solids in three dimensions"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Cubes can easily be arranged to fill three-dimensional space completely, the most natural packing being the <a href="/wiki/Cubic_honeycomb" title="Cubic honeycomb">cubic honeycomb</a>. No other <a href="/wiki/Platonic_solid" title="Platonic solid">Platonic solid</a> can tile space on its own, but some preliminary results are known. <a href="/wiki/Tetrahedra" class="mw-redirect" title="Tetrahedra">Tetrahedra</a> can achieve a packing of at least 85%. One of the best packings of regular <a href="/wiki/Dodecahedron" title="Dodecahedron">dodecahedra</a> is based on the aforementioned face-centered cubic (FCC) lattice. </p><p>Tetrahedra and <a href="/wiki/Octahedra" class="mw-redirect" title="Octahedra">octahedra</a> together can fill all of space in an arrangement known as the <a href="/wiki/Tetrahedral-octahedral_honeycomb" title="Tetrahedral-octahedral honeycomb">tetrahedral-octahedral honeycomb</a>. </p> <table class="wikitable"> <tbody><tr> <th>Solid </th> <th>Optimal density of a lattice packing </th></tr> <tr> <td><a href="/wiki/Icosahedron" title="Icosahedron">icosahedron</a> </td> <td>0.836357...<sup id="cite_ref-Betke_10-0" class="reference"><a href="#cite_note-Betke-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>dodecahedron </td> <td>(5 + <span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">5</span></span>)/8 = 0.904508...<sup id="cite_ref-Betke_10-1" class="reference"><a href="#cite_note-Betke-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </td></tr> <tr> <td>octahedron </td> <td>18/19 = 0.947368...<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> </td></tr></tbody></table> <p>Simulations combining local improvement methods with random packings suggest that the lattice packings for icosahedra, dodecahedra, and octahedra are optimal in the broader class of all packings.<sup id="cite_ref-Torquato_3-1" class="reference"><a href="#cite_note-Torquato-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Packing_in_3-dimensional_containers">Packing in 3-dimensional containers</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=5" title="Edit section: Packing in 3-dimensional containers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-default-size mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:9L_cube_puzzle_solution.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9f/9L_cube_puzzle_solution.svg/220px-9L_cube_puzzle_solution.svg.png" decoding="async" width="220" height="138" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9f/9L_cube_puzzle_solution.svg/330px-9L_cube_puzzle_solution.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9f/9L_cube_puzzle_solution.svg/440px-9L_cube_puzzle_solution.svg.png 2x" data-file-width="512" data-file-height="320" /></a><figcaption>Packing nine L tricubes into a cube</figcaption></figure> <div class="mw-heading mw-heading3"><h3 id="Different_cuboids_into_a_cuboid">Different cuboids into a cuboid</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=6" title="Edit section: Different cuboids into a cuboid"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Determine the minimum number of <a href="/wiki/Cuboid" title="Cuboid">cuboid</a> containers (bins) that are required to pack a given set of item cuboids. The rectangular cuboids to be packed can be rotated by 90 degrees on each axis. </p> <div class="mw-heading mw-heading3"><h3 id="Spheres_into_a_Euclidean_ball">Spheres into a Euclidean ball</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=7" title="Edit section: Spheres into a Euclidean ball"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Sphere_packing_in_a_sphere" title="Sphere packing in a sphere">Sphere packing in a sphere</a></div> <p>The problem of finding the smallest ball such that <span class="texhtml mvar" style="font-style:italic;">k</span> <a href="/wiki/Disjoint_sets" title="Disjoint sets">disjoint</a> open <a href="/wiki/Unit_ball" class="mw-redirect" title="Unit ball">unit balls</a> may be packed inside it has a simple and complete answer in <span class="texhtml mvar" style="font-style:italic;">n</span>-dimensional Euclidean space if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\leq n+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≤</mo> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\leq n+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/19bbdf7cb4b4e65fb604eca9a85d11fcbb2820fa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.707ex; height:2.343ex;" alt="{\displaystyle k\leq n+1}"></span>, and in an infinite-dimensional <a href="/wiki/Hilbert_space" title="Hilbert space">Hilbert space</a> with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration of <span class="texhtml mvar" style="font-style:italic;">k</span> pairwise <a href="/wiki/Tangent#Tangent_circles" title="Tangent">tangent</a> unit balls is available. People place the centers at the vertices <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},\dots ,a_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{1},\dots ,a_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed5c6512d08d64873d79d51a42e6b057007d1f7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.781ex; height:2.009ex;" alt="{\displaystyle a_{1},\dots ,a_{k}}"></span> of a regular <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (k-1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mi>k</mi> <mo>−</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (k-1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e69f74fa2adbbab50f6969acb2af719045435461" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.023ex; height:2.843ex;" alt="{\displaystyle (k-1)}"></span> dimensional <a href="/wiki/Simplex" title="Simplex">simplex</a> with edge 2; this is easily realized starting from an <a href="/wiki/Orthonormal_basis" title="Orthonormal basis">orthonormal basis</a>. A small computation shows that the distance of each vertex from the barycenter is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> </mrow> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>k</mi> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/06eebb4860331a264613cf24f245c344b5611181" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:11.311ex; height:4.843ex;" alt="{\textstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}"></span>. Moreover, any other point of the space necessarily has a larger distance from <i>at least</i> one of the <span class="texhtml mvar" style="font-style:italic;">k</span> vertices. In terms of inclusions of balls, the <span class="texhtml mvar" style="font-style:italic;">k</span> open unit balls centered at <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1},\dots ,a_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{1},\dots ,a_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed5c6512d08d64873d79d51a42e6b057007d1f7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.781ex; height:2.009ex;" alt="{\displaystyle a_{1},\dots ,a_{k}}"></span> are included in a ball of radius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo>:=</mo> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> </mrow> <mn>1</mn> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mi>k</mi> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6591e253363caf36d3b13e349621f12878000aa3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:21.197ex; height:4.843ex;" alt="{\textstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}"></span>, which is minimal for this configuration. </p><p>To show that this configuration is optimal, let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\dots ,x_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{1},\dots ,x_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/49099bbc969b384b05477fd616862198234d9d5c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.981ex; height:2.009ex;" alt="{\displaystyle x_{1},\dots ,x_{k}}"></span> be the centers of <span class="texhtml mvar" style="font-style:italic;">k</span> disjoint open unit balls contained in a ball of radius <span class="texhtml mvar" style="font-style:italic;">r</span> centered at a point <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/86f21d0e31751534cd6584264ecf864a6aa792cf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}"></span>. Consider the <a href="/wiki/Function_(mathematics)" title="Function (mathematics)">map</a> from the finite set <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{x_{1},\dots ,x_{k}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{x_{1},\dots ,x_{k}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f7851bd2e6f7c22eeb477cc31ad079ae22437675" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.305ex; height:2.843ex;" alt="{\displaystyle \{x_{1},\dots ,x_{k}\}}"></span> into <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{a_{1},\dots ,a_{k}\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{a_{1},\dots ,a_{k}\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dda4b7182c2cc5413a82f17b3f50f61a3f389ea" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.106ex; height:2.843ex;" alt="{\displaystyle \{a_{1},\dots ,a_{k}\}}"></span> taking <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5db47cb3d2f9496205a17a6856c91c1d3d363ccd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.239ex; height:2.343ex;" alt="{\displaystyle x_{j}}"></span> in the corresponding <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d0096fb78d6843c9fb67a840dc796b61ad93eec2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.14ex; height:2.343ex;" alt="{\displaystyle a_{j}}"></span> for each <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq j\leq k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>≤</mo> <mi>j</mi> <mo>≤</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe6213470ed1ea7817e7bec06ffa56be9f5e7721" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.529ex; height:2.509ex;" alt="{\displaystyle 1\leq j\leq k}"></span>. Since for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq i<j\leq k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>≤</mo> <mi>i</mi> <mo><</mo> <mi>j</mi> <mo>≤</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1\leq i<j\leq k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0ac845570b060e53af400e8ee2ade6c7dd844546" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.43ex; height:2.509ex;" alt="{\displaystyle 1\leq i<j\leq k}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> <mo>=</mo> <mn>2</mn> <mo>≤</mo> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo>−</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d67ec906fcc6d31b25fccb4326473a7aa141502b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:26.228ex; height:3.009ex;" alt="{\displaystyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}"></span> this map is 1-<a href="/wiki/Lipschitz_continuity" title="Lipschitz continuity">Lipschitz</a> and by the <a href="/wiki/Kirszbraun_theorem" title="Kirszbraun theorem">Kirszbraun theorem</a> it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a_{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/693ad9f934775838bd72406b41ada4a59785d7ba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.284ex; height:2.009ex;" alt="{\displaystyle a_{0}}"></span> such that for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\leq j\leq k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>≤</mo> <mi>j</mi> <mo>≤</mo> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fe6213470ed1ea7817e7bec06ffa56be9f5e7721" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.529ex; height:2.509ex;" alt="{\displaystyle 1\leq j\leq k}"></span> one has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> <mo>≤</mo> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e845e8e690a60cebaab56fb62b9efe88d10307e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.476ex; height:3.009ex;" alt="{\displaystyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}"></span>, so that also <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> <mo>≤</mo> <mn>1</mn> <mo>+</mo> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>a</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> <mo>≤</mo> <mn>1</mn> <mo>+</mo> <mo fence="false" stretchy="false">‖</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>−</mo> <msub> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo fence="false" stretchy="false">‖</mo> <mo>≤</mo> <mi>r</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/abf3a0eb4a5cc0b4882b7015b503f281d6cb3c24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:39.865ex; height:3.009ex;" alt="{\displaystyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}"></span>. This shows that there are <span class="texhtml mvar" style="font-style:italic;">k</span> disjoint unit open balls in a ball of radius <span class="texhtml mvar" style="font-style:italic;">r</span> <a href="/wiki/If_and_only_if" title="If and only if">if and only if</a> <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\geq r_{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>≥</mo> <msub> <mi>r</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\geq r_{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8643f679d1951387baec08ea2017e41ca83f400c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.284ex; height:2.343ex;" alt="{\displaystyle r\geq r_{k}}"></span>. Notice that in an infinite-dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius <span class="texhtml mvar" style="font-style:italic;">r</span> if and only if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\geq 1+{\sqrt {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>≥</mo> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\geq 1+{\sqrt {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ef9ae55ee1678e02eefa8bbd7bbec8a040a97898" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.248ex; height:3.009ex;" alt="{\displaystyle r\geq 1+{\sqrt {2}}}"></span>. For instance, the unit balls centered at <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {2}}e_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> </msqrt> </mrow> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\sqrt {2}}e_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3696f9ef2c76022cb18746d381363c524f2e5fd6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.092ex; height:3.343ex;" alt="{\displaystyle {\sqrt {2}}e_{j}}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{e_{j}\}_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <msub> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{e_{j}\}_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/675bf3a4609162909571e68b927013bc6c5cfba8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.228ex; height:3.009ex;" alt="{\displaystyle \{e_{j}\}_{j}}"></span> is an orthonormal basis, are disjoint and included in a ball of radius <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+{\sqrt {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1+{\sqrt {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0d6647fc0b70302f56dbc87eaf718dc3832ba161" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.101ex; height:3.009ex;" alt="{\displaystyle 1+{\sqrt {2}}}"></span> centered at the origin. Moreover, for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r<1+{\sqrt {2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo><</mo> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>2</mn> </msqrt> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r<1+{\sqrt {2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0aa025d75c5736a94dcbf9b0db1206c00dc045dc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.248ex; height:3.009ex;" alt="{\displaystyle r<1+{\sqrt {2}}}"></span>, the maximum number of disjoint open unit balls inside a ball of radius <span class="texhtml mvar" style="font-style:italic;">r</span> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">⌊</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>2</mn> <mrow> <mn>2</mn> <mo>−</mo> <mo stretchy="false">(</mo> <mi>r</mi> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.2em" minsize="1.2em">⌋</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b7d6b4a9b54916ea2b61ea405adc418983b1dc1b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:10.084ex; height:4.509ex;" alt="{\textstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Spheres_in_a_cuboid">Spheres in a cuboid</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=8" title="Edit section: Spheres in a cuboid"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">See also: <a href="/wiki/Sphere_packing_in_a_cube" title="Sphere packing in a cube">Sphere packing in a cube</a></div> <p>People determine the number of spherical objects of given diameter <span class="texhtml mvar" style="font-style:italic;">d</span> that can be packed into a cuboid of size <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\times b\times c}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>a</mi> <mo>×</mo> <mi>b</mi> <mo>×</mo> <mi>c</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle a\times b\times c}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d8dc3b01443c2edcec21c58d0c3bcca2ea99ec9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.915ex; height:2.176ex;" alt="{\displaystyle a\times b\times c}"></span>. </p> <div class="mw-heading mw-heading3"><h3 id="Identical_spheres_in_a_cylinder">Identical spheres in a cylinder</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=9" title="Edit section: Identical spheres in a cylinder"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Sphere_packing_in_a_cylinder" title="Sphere packing in a cylinder">Sphere packing in a cylinder</a></div> <p>People determine the minimum height <span class="texhtml mvar" style="font-style:italic;">h</span> of a <a href="/wiki/Cylinder" title="Cylinder">cylinder</a> with given radius <span class="texhtml mvar" style="font-style:italic;">R</span> that will pack <span class="texhtml mvar" style="font-style:italic;">n</span> identical spheres of radius <span class="texhtml"><i>r</i> (< <i>R</i>)</span>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> For a small radius <span class="texhtml mvar" style="font-style:italic;">R</span> the spheres arrange to ordered structures, called <a href="/wiki/Columnar_structure" class="mw-redirect" title="Columnar structure">columnar structures</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Polyhedra_in_spheres">Polyhedra in spheres</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=10" title="Edit section: Polyhedra in spheres"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>People determine the minimum radius <span class="texhtml mvar" style="font-style:italic;">R</span> that will pack <span class="texhtml mvar" style="font-style:italic;">n</span> identical, unit <a href="/wiki/Volume" title="Volume">volume</a> <a href="/wiki/Polyhedra" class="mw-redirect" title="Polyhedra">polyhedra</a> of a given shape.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Packing_in_2-dimensional_containers">Packing in 2-dimensional containers</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=11" title="Edit section: Packing in 2-dimensional containers"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Disk_pack10.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Disk_pack10.svg/120px-Disk_pack10.svg.png" decoding="async" width="120" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Disk_pack10.svg/180px-Disk_pack10.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/6a/Disk_pack10.svg/240px-Disk_pack10.svg.png 2x" data-file-width="382" data-file-height="382" /></a><figcaption>The optimal packing of 10 circles in a circle</figcaption></figure><p>Many variants of 2-dimensional packing problems have been studied. </p><div class="mw-heading mw-heading3"><h3 id="Packing_of_circles">Packing of circles</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=12" title="Edit section: Packing of circles"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Circle_packing" title="Circle packing">Circle packing</a></div> <p>People are given <span class="texhtml mvar" style="font-style:italic;">n</span> <a href="/wiki/Unit_circle" title="Unit circle">unit circles</a>, and have to pack them in the smallest possible container. Several kinds of containers have been studied: </p> <ul><li><a href="/wiki/Circle_packing_in_a_circle" title="Circle packing in a circle">Packing circles in a <b>circle</b></a> - closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, <span class="texhtml mvar" style="font-style:italic;">d<sub>n</sub></span>, between points. Optimal solutions have been proven for <span class="texhtml"><i>n</i> ≤ 13</span>, and <span class="texhtml"><i>n</i> = 19</span>.</li> <li><a href="/wiki/Circle_packing_in_a_square" title="Circle packing in a square">Packing circles in a <b>square</b></a> - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, <span class="texhtml mvar" style="font-style:italic;">d<sub>n</sub></span>, between points. To convert between these two formulations of the problem, the square side for unit circles will be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L=2+2/d_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>=</mo> <mn>2</mn> <mo>+</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msub> <mi>d</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L=2+2/d_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/330cbf4f08949a41aa95b33e5d19e59484e93fb2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.436ex; height:2.843ex;" alt="{\displaystyle L=2+2/d_{n}}"></span>. <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:15_circles_in_a_square.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/ee/15_circles_in_a_square.svg/120px-15_circles_in_a_square.svg.png" decoding="async" width="120" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/ee/15_circles_in_a_square.svg/180px-15_circles_in_a_square.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/ee/15_circles_in_a_square.svg/240px-15_circles_in_a_square.svg.png 2x" data-file-width="512" data-file-height="512" /></a><figcaption>The optimal packing of 15 circles in a square</figcaption></figure>Optimal solutions have been proven for <span class="texhtml"><i>n</i> ≤ 30</span>.</li> <li><a href="/wiki/Circle_packing_in_a_rectangle" class="mw-redirect" title="Circle packing in a rectangle">Packing circles in a <b>rectangle</b></a></li> <li><a href="/wiki/Circle_packing_in_an_isosceles_right_triangle" title="Circle packing in an isosceles right triangle">Packing circles in an <b>isosceles right triangle</b></a> - good estimates are known for <span class="texhtml"><i>n</i> < 300</span>.</li> <li><a href="/wiki/Circle_packing_in_an_equilateral_triangle" title="Circle packing in an equilateral triangle">Packing circles in an <b>equilateral triangle</b></a> - Optimal solutions are known for <span class="texhtml"><i>n</i> < 13</span>, and <a href="/wiki/Conjecture" title="Conjecture">conjectures</a> are available for <span class="texhtml"><i>n</i> < 28</span>.<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup></li></ul> <p><span class="anchor" id="Packing_squares"></span> </p> <div class="mw-heading mw-heading3"><h3 id="Packing_of_squares">Packing of squares</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=13" title="Edit section: Packing of squares"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Square_packing" title="Square packing">Square packing</a></div> <p>People are given <span class="texhtml mvar" style="font-style:italic;">n</span> <a href="/wiki/Unit_square" title="Unit square">unit squares</a> and have to pack them into the smallest possible container, where the container type varies: </p> <ul><li><a href="/wiki/Square_packing_in_a_square" class="mw-redirect" title="Square packing in a square">Packing squares in a <b>square</b></a>: Optimal solutions have been proven for <span class="texhtml mvar" style="font-style:italic;">n</span> from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and any <a href="/wiki/Square_number" title="Square number">square</a> <a href="/wiki/Integer" title="Integer">integer</a>. The wasted space is asymptotically <span class="texhtml"><a href="/wiki/Big_O_notation" title="Big O notation">O</a>(<i>a</i><sup>3/5</sup>)</span>.</li> <li><a href="/wiki/Square_packing_in_a_circle" class="mw-redirect" title="Square packing in a circle">Packing squares in a <b>circle</b></a>: Good solutions are known for <span class="texhtml"><i>n</i> ≤ 35</span>.<figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:10_kvadratoj_en_kvadrato.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/10_kvadratoj_en_kvadrato.svg/120px-10_kvadratoj_en_kvadrato.svg.png" decoding="async" width="120" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/10_kvadratoj_en_kvadrato.svg/180px-10_kvadratoj_en_kvadrato.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4c/10_kvadratoj_en_kvadrato.svg/240px-10_kvadratoj_en_kvadrato.svg.png 2x" data-file-width="800" data-file-height="800" /></a><figcaption>The optimal packing of 10 squares in a square</figcaption></figure></li></ul> <div class="mw-heading mw-heading3"><h3 id="Packing_of_rectangles">Packing of rectangles</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=14" title="Edit section: Packing of rectangles"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="/wiki/Rectangle_packing" title="Rectangle packing">Rectangle packing</a></div> <ul><li><b>Packing identical rectangles in a rectangle</b>: The problem of packing multiple instances of a single <a href="/wiki/Rectangle" title="Rectangle">rectangle</a> of size <span class="texhtml">(<i>l</i>,<i>w</i>)</span>, allowing for 90° rotation, in a bigger rectangle of size <span class="texhtml">(<i>L</i>,<i>W</i> )</span> has some applications such as loading of boxes on pallets and, specifically, <a href="/wiki/Woodpulp" class="mw-redirect" title="Woodpulp">woodpulp</a> stowage. For example, it is possible to pack 147 rectangles of size (137,95) in a rectangle of size (1600,1230).</li> <li><b>Packing different rectangles in a rectangle</b>: The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum <a href="/wiki/Area" title="Area">area</a> (but with no boundaries on the enclosing rectangle's width or height) has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is <a href="/wiki/NP-complete" class="mw-redirect" title="NP-complete">NP-complete</a> in general, but there are fast algorithms for solving small instances.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Related_fields">Related fields</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=15" title="Edit section: Related fields"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In tiling or <a href="/wiki/Tessellation" title="Tessellation">tessellation</a> problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing rectangles or <a href="/wiki/Polyomino" title="Polyomino">polyominoes</a> into a larger rectangle or other square-like shape. </p><p>There are significant <a href="/wiki/Theorem" title="Theorem">theorems</a> on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps: </p> <dl><dd>An <i>a</i> × <i>b</i> rectangle can be packed with 1 × <i>n</i> strips if and only if <i>n</i> divides <i>a</i> or <i>n</i> divides <i>b</i>.<sup id="cite_ref-Gems2_15-0" class="reference"><a href="#cite_note-Gems2-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Klarner_16-0" class="reference"><a href="#cite_note-Klarner-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup></dd> <dd><a href="/wiki/De_Bruijn%27s_theorem" title="De Bruijn's theorem">de Bruijn's theorem</a>: A box can be packed with a <a href="/wiki/Harmonic_brick" class="mw-redirect" title="Harmonic brick">harmonic brick</a> <i>a</i> × <i>a b</i> × <i>a b c</i> if the box has dimensions <i>a p</i> × <i>a b q</i> × <i>a b c r</i> for some <a href="/wiki/Natural_number" title="Natural number">natural numbers</a> <i>p</i>, <i>q</i>, <i>r</i> (i.e., the box is a multiple of the brick.)<sup id="cite_ref-Gems2_15-1" class="reference"><a href="#cite_note-Gems2-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></dd></dl> <p>The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with <a href="/wiki/Congruence_(geometry)" title="Congruence (geometry)">congruent</a> tiles, and to pack one of each <i>n</i>-omino into a rectangle. </p><p>A classic puzzle of the second kind is to arrange all twelve <a href="/wiki/Pentomino" title="Pentomino">pentominoes</a> into rectangles sized 3×20, 4×15, 5×12 or 6×10. </p> <div class="mw-heading mw-heading2"><h2 id="Packing_of_irregular_objects">Packing of irregular objects</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=16" title="Edit section: Packing of irregular objects"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Packing of irregular objects is a problem not lending itself well to closed form solutions; however, the applicability to practical environmental science is quite important. For example, irregularly shaped soil particles pack differently as the sizes and shapes vary, leading to important outcomes for plant species to adapt root formations and to allow water movement in the soil.<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </p><p>The problem of deciding whether a given set of <a href="/wiki/Polygon" title="Polygon">polygons</a> can fit in a given square container has been shown to be complete for the <a href="/wiki/Existential_theory_of_the_reals" title="Existential theory of the reals">existential theory of the reals</a>.<sup id="cite_ref-18" class="reference"><a href="#cite_note-18"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=17" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Bin_packing_problem" title="Bin packing problem">Bin packing problem</a></li> <li><a href="/wiki/Close-packing_of_equal_spheres" title="Close-packing of equal spheres">Close-packing of equal spheres</a></li> <li><a href="/wiki/Conway_puzzle" title="Conway puzzle">Conway puzzle</a></li> <li><a href="/wiki/Covering_problem" class="mw-redirect" title="Covering problem">Covering problem</a></li> <li><a href="/wiki/Cutting_stock_problem" title="Cutting stock problem">Cutting stock problem</a></li> <li><a href="/wiki/Ellipsoid_packing" title="Ellipsoid packing">Ellipsoid packing</a></li> <li><a href="/wiki/Kissing_number_problem" class="mw-redirect" title="Kissing number problem">Kissing number problem</a></li> <li><a href="/wiki/Knapsack_problem" title="Knapsack problem">Knapsack problem</a></li> <li><a href="/wiki/Random_close_pack" title="Random close pack">Random close pack</a></li> <li><a href="/wiki/Set_packing" title="Set packing">Set packing</a></li> <li><a href="/wiki/Slothouber%E2%80%93Graatsma_puzzle" title="Slothouber–Graatsma puzzle">Slothouber–Graatsma puzzle</a></li> <li><a href="/wiki/Strip_packing_problem" title="Strip packing problem">Strip packing problem</a></li> <li><a href="/wiki/Tetrahedron_packing" title="Tetrahedron packing">Tetrahedron packing</a></li> <li><a href="/wiki/Tetris" title="Tetris">Tetris</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=18" title="Edit section: Notes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;"> <ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFLodi,_A.Martello,_S.Monaci,_M.2002" class="citation journal cs1">Lodi, A.; Martello, S.; Monaci, M. (2002). "Two-dimensional packing problems: A survey". <i>European Journal of Operational Research</i>. <b>141</b> (2). Elsevier: 241–252. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0377-2217%2802%2900123-6">10.1016/s0377-2217(02)00123-6</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=European+Journal+of+Operational+Research&rft.atitle=Two-dimensional+packing+problems%3A+A+survey&rft.volume=141&rft.issue=2&rft.pages=241-252&rft.date=2002&rft_id=info%3Adoi%2F10.1016%2Fs0377-2217%2802%2900123-6&rft.au=Lodi%2C+A.&rft.au=Martello%2C+S.&rft.au=Monaci%2C+M.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFDonevStillingerChaikinTorquato2004" class="citation journal cs1">Donev, A.; Stillinger, F.; Chaikin, P.; Torquato, S. (2004). "Unusually Dense Crystal Packings of Ellipsoids". <i>Physical Review Letters</i>. <b>92</b> (25): 255506. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cond-mat/0403286">cond-mat/0403286</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2004PhRvL..92y5506D">2004PhRvL..92y5506D</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevLett.92.255506">10.1103/PhysRevLett.92.255506</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/15245027">15245027</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:7982407">7982407</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Physical+Review+Letters&rft.atitle=Unusually+Dense+Crystal+Packings+of+Ellipsoids&rft.volume=92&rft.issue=25&rft.pages=255506&rft.date=2004&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7982407%23id-name%3DS2CID&rft_id=info%3Abibcode%2F2004PhRvL..92y5506D&rft_id=info%3Aarxiv%2Fcond-mat%2F0403286&rft_id=info%3Apmid%2F15245027&rft_id=info%3Adoi%2F10.1103%2FPhysRevLett.92.255506&rft.aulast=Donev&rft.aufirst=A.&rft.au=Stillinger%2C+F.&rft.au=Chaikin%2C+P.&rft.au=Torquato%2C+S.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-Torquato-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-Torquato_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Torquato_3-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTorquatoJiao2009" class="citation journal cs1">Torquato, S.; Jiao, Y. (August 2009). "Dense packings of the Platonic and Archimedean solids". <i>Nature</i>. <b>460</b> (7257): 876–879. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/0908.4107">0908.4107</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009Natur.460..876T">2009Natur.460..876T</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fnature08239">10.1038/nature08239</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0028-0836">0028-0836</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/19675649">19675649</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:52819935">52819935</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nature&rft.atitle=Dense+packings+of+the+Platonic+and+Archimedean+solids&rft.volume=460&rft.issue=7257&rft.pages=876-879&rft.date=2009-08&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A52819935%23id-name%3DS2CID&rft_id=info%3Abibcode%2F2009Natur.460..876T&rft_id=info%3Aarxiv%2F0908.4107&rft.issn=0028-0836&rft_id=info%3Adoi%2F10.1038%2Fnature08239&rft_id=info%3Apmid%2F19675649&rft.aulast=Torquato&rft.aufirst=S.&rft.au=Jiao%2C+Y.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHaji-AkbariEngelKeysZheng2009" class="citation journal cs1">Haji-Akbari, A.; Engel, M.; Keys, A. S.; Zheng, X.; Petschek, R. G.; Palffy-Muhoray, P.; Glotzer, S. C. (2009). "Disordered, quasicrystalline and crystalline phases of densely packed tetrahedra". <i>Nature</i>. <b>462</b> (7274): 773–777. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1012.5138">1012.5138</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009Natur.462..773H">2009Natur.462..773H</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fnature08641">10.1038/nature08641</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/20010683">20010683</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:4412674">4412674</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nature&rft.atitle=Disordered%2C+quasicrystalline+and+crystalline+phases+of+densely+packed+tetrahedra&rft.volume=462&rft.issue=7274&rft.pages=773-777&rft.date=2009&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A4412674%23id-name%3DS2CID&rft_id=info%3Abibcode%2F2009Natur.462..773H&rft_id=info%3Aarxiv%2F1012.5138&rft_id=info%3Apmid%2F20010683&rft_id=info%3Adoi%2F10.1038%2Fnature08641&rft.aulast=Haji-Akbari&rft.aufirst=A.&rft.au=Engel%2C+M.&rft.au=Keys%2C+A.+S.&rft.au=Zheng%2C+X.&rft.au=Petschek%2C+R.+G.&rft.au=Palffy-Muhoray%2C+P.&rft.au=Glotzer%2C+S.+C.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChenEngelGlotzer2010" class="citation journal cs1">Chen, E. R.; Engel, M.; Glotzer, S. C. (2010). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00454-010-9273-0">"Dense Crystalline Dimer Packings of Regular Tetrahedra"</a>. <i><a href="/wiki/Discrete_%26_Computational_Geometry" title="Discrete & Computational Geometry">Discrete & Computational Geometry</a></i>. <b>44</b> (2): 253–280. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1001.0586">1001.0586</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010arXiv1001.0586C">2010arXiv1001.0586C</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs00454-010-9273-0">10.1007/s00454-010-9273-0</a></span>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18523116">18523116</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+%26+Computational+Geometry&rft.atitle=Dense+Crystalline+Dimer+Packings+of+Regular+Tetrahedra&rft.volume=44&rft.issue=2&rft.pages=253-280&rft.date=2010&rft_id=info%3Aarxiv%2F1001.0586&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A18523116%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2Fs00454-010-9273-0&rft_id=info%3Abibcode%2F2010arXiv1001.0586C&rft.aulast=Chen&rft.aufirst=E.+R.&rft.au=Engel%2C+M.&rft.au=Glotzer%2C+S.+C.&rft_id=https%3A%2F%2Fdoi.org%2F10.1007%252Fs00454-010-9273-0&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStein1995" class="citation cs2"><a href="/wiki/Sherman_K._Stein" title="Sherman K. Stein">Stein, Sherman K.</a> (March 1995), "Packing tripods", Mathematical entertainments, <i><a href="/wiki/The_Mathematical_Intelligencer" title="The Mathematical Intelligencer">The Mathematical Intelligencer</a></i>, <b>17</b> (2): 37–39, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbf03024896">10.1007/bf03024896</a>, <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:124703268">124703268</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=The+Mathematical+Intelligencer&rft.atitle=Packing+tripods&rft.volume=17&rft.issue=2&rft.pages=37-39&rft.date=1995-03&rft_id=info%3Adoi%2F10.1007%2Fbf03024896&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A124703268%23id-name%3DS2CID&rft.aulast=Stein&rft.aufirst=Sherman+K.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span>. Reprinted in <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGale1998" class="citation cs2">Gale, David (1998), Gale, David (ed.), <i>Tracking the Automatic ANT</i>, Springer-Verlag, pp. 131–136, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4612-2192-0">10.1007/978-1-4612-2192-0</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-387-98272-8" title="Special:BookSources/0-387-98272-8"><bdi>0-387-98272-8</bdi></a>, <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1661863">1661863</a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Tracking+the+Automatic+ANT&rft.pages=131-136&rft.pub=Springer-Verlag&rft.date=1998&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1661863%23id-name%3DMR&rft_id=info%3Adoi%2F10.1007%2F978-1-4612-2192-0&rft.isbn=0-387-98272-8&rft.aulast=Gale&rft.aufirst=David&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHudsonHarrowell2011" class="citation journal cs1">Hudson, T. S.; Harrowell, P. (2011). "Structural searches using isopointal sets as generators: Densest packings for binary hard sphere mixtures". <i>Journal of Physics: Condensed Matter</i>. <b>23</b> (19): 194103. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2011JPCM...23s4103H">2011JPCM...23s4103H</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1088%2F0953-8984%2F23%2F19%2F194103">10.1088/0953-8984/23/19/194103</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/21525553">21525553</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:25505460">25505460</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Physics%3A+Condensed+Matter&rft.atitle=Structural+searches+using+isopointal+sets+as+generators%3A+Densest+packings+for+binary+hard+sphere+mixtures&rft.volume=23&rft.issue=19&rft.pages=194103&rft.date=2011&rft_id=info%3Adoi%2F10.1088%2F0953-8984%2F23%2F19%2F194103&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A25505460%23id-name%3DS2CID&rft_id=info%3Apmid%2F21525553&rft_id=info%3Abibcode%2F2011JPCM...23s4103H&rft.aulast=Hudson&rft.aufirst=T.+S.&rft.au=Harrowell%2C+P.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/CirclePacking.html">"Circle Packing"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Circle+Packing&rft_id=http%3A%2F%2Fmathworld.wolfram.com%2FCirclePacking.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSmalley1963" class="citation journal cs1">Smalley, I.J. (1963). "Simple regular sphere packings in three dimensions". <i>Mathematics Magazine</i>. <b>36</b> (5): 295–299. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2688954">10.2307/2688954</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2688954">2688954</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Mathematics+Magazine&rft.atitle=Simple+regular+sphere+packings+in+three+dimensions&rft.volume=36&rft.issue=5&rft.pages=295-299&rft.date=1963&rft_id=info%3Adoi%2F10.2307%2F2688954&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2688954%23id-name%3DJSTOR&rft.aulast=Smalley&rft.aufirst=I.J.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-Betke-10"><span class="mw-cite-backlink">^ <a href="#cite_ref-Betke_10-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Betke_10-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBetkeHenk2000" class="citation journal cs1">Betke, Ulrich; Henk, Martin (2000). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0925-7721%2800%2900007-9">"Densest lattice packings of 3-polytopes"</a>. <i><a href="/wiki/Computational_Geometry_(journal)" title="Computational Geometry (journal)">Computational Geometry</a></i>. <b>16</b> (3): 157–186. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/math/9909172">math/9909172</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0925-7721%2800%2900007-9">10.1016/S0925-7721(00)00007-9</a></span>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=1765181">1765181</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12118403">12118403</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Computational+Geometry&rft.atitle=Densest+lattice+packings+of+3-polytopes&rft.volume=16&rft.issue=3&rft.pages=157-186&rft.date=2000&rft_id=info%3Aarxiv%2Fmath%2F9909172&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D1765181%23id-name%3DMR&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A12118403%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2FS0925-7721%2800%2900007-9&rft.aulast=Betke&rft.aufirst=Ulrich&rft.au=Henk%2C+Martin&rft_id=https%3A%2F%2Fdoi.org%2F10.1016%252FS0925-7721%252800%252900007-9&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Minkowski, H. Dichteste gitterförmige Lagerung kongruenter Körper. <i>Nachr. Akad. Wiss. Göttingen Math. Phys. KI. II</i> 311–355 (1904).</span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStoyanYaskov2010" class="citation journal cs1">Stoyan, Y. G.; Yaskov, G. N. (2010). "Packing identical spheres into a cylinder". <i>International Transactions in Operational Research</i>. <b>17</b>: 51–70. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.1475-3995.2009.00733.x">10.1111/j.1475-3995.2009.00733.x</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=International+Transactions+in+Operational+Research&rft.atitle=Packing+identical+spheres+into+a+cylinder&rft.volume=17&rft.pages=51-70&rft.date=2010&rft_id=info%3Adoi%2F10.1111%2Fj.1475-3995.2009.00733.x&rft.aulast=Stoyan&rft.aufirst=Y.+G.&rft.au=Yaskov%2C+G.+N.&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTeichvan_AndersKlotsaDshemuchadse2016" class="citation journal cs1">Teich, E.G.; van Anders, G.; Klotsa, D.; Dshemuchadse, J.; Glotzer, S.C. (2016). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4760782">"Clusters of Polyhedra in Spherical Confinement"</a>. <i>Proc. Natl. Acad. Sci. U.S.A</i>. <b>113</b> (6): E669–E678. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016PNAS..113E.669T">2016PNAS..113E.669T</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.1524875113">10.1073/pnas.1524875113</a></span>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4760782">4760782</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/26811458">26811458</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proc.+Natl.+Acad.+Sci.+U.S.A.&rft.atitle=Clusters+of+Polyhedra+in+Spherical+Confinement&rft.volume=113&rft.issue=6&rft.pages=E669-E678&rft.date=2016&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC4760782%23id-name%3DPMC&rft_id=info%3Apmid%2F26811458&rft_id=info%3Adoi%2F10.1073%2Fpnas.1524875113&rft_id=info%3Abibcode%2F2016PNAS..113E.669T&rft.aulast=Teich&rft.aufirst=E.G.&rft.au=van+Anders%2C+G.&rft.au=Klotsa%2C+D.&rft.au=Dshemuchadse%2C+J.&rft.au=Glotzer%2C+S.C.&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC4760782&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMelissen1995" class="citation journal cs1">Melissen, J. (1995). <a rel="nofollow" class="external text" href="https://research.utwente.nl/en/publications/packing-16-17-of-18-circles-in-an-equilateral-triangle(b2172f19-9654-4ff1-9af4-59da1b6bef3d).html">"Packing 16, 17 or 18 circles in an equilateral triangle"</a>. <i>Discrete Mathematics</i>. <b>145</b> (1–3): 333–342. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2895%2990139-C">10.1016/0012-365X(95)90139-C</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Discrete+Mathematics&rft.atitle=Packing+16%2C+17+or+18+circles+in+an+equilateral+triangle&rft.volume=145&rft.issue=1%E2%80%933&rft.pages=333-342&rft.date=1995&rft_id=info%3Adoi%2F10.1016%2F0012-365X%2895%2990139-C&rft.aulast=Melissen&rft.aufirst=J.&rft_id=https%3A%2F%2Fresearch.utwente.nl%2Fen%2Fpublications%2Fpacking-16-17-of-18-circles-in-an-equilateral-triangle%28b2172f19-9654-4ff1-9af4-59da1b6bef3d%29.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-Gems2-15"><span class="mw-cite-backlink">^ <a href="#cite_ref-Gems2_15-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Gems2_15-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHonsberger1976" class="citation book cs1">Honsberger, Ross (1976). <i>Mathematical Gems II</i>. <a href="/wiki/The_Mathematical_Association_of_America" class="mw-redirect" title="The Mathematical Association of America">The Mathematical Association of America</a>. p. 67. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-88385-302-7" title="Special:BookSources/0-88385-302-7"><bdi>0-88385-302-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Mathematical+Gems+II&rft.pages=67&rft.pub=The+Mathematical+Association+of+America&rft.date=1976&rft.isbn=0-88385-302-7&rft.aulast=Honsberger&rft.aufirst=Ross&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-Klarner-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-Klarner_16-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKlarnerHautus1971" class="citation journal cs1"><a href="/wiki/David_A._Klarner" title="David A. Klarner">Klarner, D.A.</a>; Hautus, M.L.J (1971). "Uniformly coloured stained glass windows". <i>Proceedings of the London Mathematical Society</i>. 3. <b>23</b> (4): 613–628. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1112%2Fplms%2Fs3-23.4.613">10.1112/plms/s3-23.4.613</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+London+Mathematical+Society&rft.atitle=Uniformly+coloured+stained+glass+windows&rft.volume=23&rft.issue=4&rft.pages=613-628&rft.date=1971&rft_id=info%3Adoi%2F10.1112%2Fplms%2Fs3-23.4.613&rft.aulast=Klarner&rft.aufirst=D.A.&rft.au=Hautus%2C+M.L.J&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text">C.Michael Hogan. 2010. <a rel="nofollow" class="external text" href="http://www.eoearth.org/article/Abiotic_factor?topic=49461"><i>Abiotic factor</i>. Encyclopedia of Earth. eds Emily Monosson and C. Cleveland. National Council for Science and the Environment</a>. Washington DC</span> </li> <li id="cite_note-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-18">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAbrahamsenMiltzowNadja2020" class="citation cs2">Abrahamsen, Mikkel; Miltzow, Tillmann; Nadja, Seiferth (2020), <i>Framework for <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \exists \mathbb {R} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">∃</mi> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">R</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \exists \mathbb {R} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4f91784ca9a3f258dd90e29f4ceab59b00264ef5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.971ex; height:2.176ex;" alt="{\displaystyle \exists \mathbb {R} }"></span>-Completeness of Two-Dimensional Packing Problems</i>, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/2004.07558">2004.07558</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Framework+for+MATH+RENDER+ERROR-Completeness+of+Two-Dimensional+Packing+Problems&rft.date=2020&rft_id=info%3Aarxiv%2F2004.07558&rft.aulast=Abrahamsen&rft.aufirst=Mikkel&rft.au=Miltzow%2C+Tillmann&rft.au=Nadja%2C+Seiferth&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span>.</span> </li> </ol></div> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=19" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><span class="citation mathworld" id="Reference-Mathworld-Klarner's_Theorem"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/KlarnersTheorem.html">"Klarner's Theorem"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=Klarner%27s+Theorem&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FKlarnersTheorem.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span></li> <li><span class="citation mathworld" id="Reference-Mathworld-de_Bruijn's_Theorem"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="/wiki/Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/deBruijnsTheorem.html">"de Bruijn's Theorem"</a>. <i><a href="/wiki/MathWorld" title="MathWorld">MathWorld</a></i>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=MathWorld&rft.atitle=de+Bruijn%27s+Theorem&rft.au=Weisstein%2C+Eric+W.&rft_id=https%3A%2F%2Fmathworld.wolfram.com%2FdeBruijnsTheorem.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3APacking+problems" class="Z3988"></span></span></li></ul> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Packing_problems&action=edit&section=20" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1235681985">.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}</style><style data-mw-deduplicate="TemplateStyles:r1237033735">@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}</style><div class="side-box side-box-right plainlinks sistersitebox"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1126788409"> <div class="side-box-flex"> <div class="side-box-image"><span class="noviewer" typeof="mw:File"><span><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/30px-Commons-logo.svg.png" decoding="async" width="30" height="40" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/45px-Commons-logo.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/4/4a/Commons-logo.svg/59px-Commons-logo.svg.png 2x" data-file-width="1024" data-file-height="1376" /></span></span></div> <div class="side-box-text plainlist">Wikimedia Commons has media related to <span style="font-weight: bold; font-style: italic;"><a href="https://commons.wikimedia.org/wiki/Category:Packing_problems" class="extiw" title="commons:Category:Packing problems">Packing problems</a></span>.</div></div> </div> <ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20190303205438/http://pdfs.semanticscholar.org/bb99/86af2f26f7726fcef1bc684eac8239c9b853.pdf">Optimizing Three-Dimensional Bin Packing</a></li></ul> <p>Many puzzle books as well as mathematical journals contain articles on packing problems. </p> <ul><li><a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/Packing.html">Links to various MathWorld articles on packing</a></li> <li><a rel="nofollow" class="external text" href="http://mathworld.wolfram.com/SquarePacking.html">MathWorld notes on packing squares.</a></li> <li><a rel="nofollow" class="external text" href="https://erich-friedman.github.io/packing/index.html">Erich's Packing Center</a></li> <li><a rel="nofollow" class="external text" href="http://www.packomania.com/">www.packomania.com</a> A site with tables, graphs, calculators, references, etc.</li> <li><a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/BoxPacking/">"Box Packing"</a> by <a href="/wiki/Ed_Pegg,_Jr." class="mw-redirect" title="Ed Pegg, Jr.">Ed Pegg, Jr.</a>, the <a href="/wiki/Wolfram_Demonstrations_Project" title="Wolfram Demonstrations Project">Wolfram Demonstrations Project</a>, 2007.</li> <li><a rel="nofollow" class="external text" href="http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html#overview">Best known packings of equal circles in a circle, up to 1100</a></li></ul> <p class="mw-empty-elt"> </p> <ul><li><a rel="nofollow" class="external text" href="http://apmonitor.com/me575/index.php/Main/CircleChallenge">Circle packing challenge problem in Python</a></li></ul> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Packing_problems" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Packing_problems" title="Template:Packing problems"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Packing_problems" title="Template talk:Packing problems"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Packing_problems" title="Special:EditPage/Template:Packing problems"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Packing_problems" style="font-size:114%;margin:0 4em"><a class="mw-selflink selflink">Packing problems</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Abstract packing</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bin_packing_problem" title="Bin packing problem">Bin</a></li> <li><a href="/wiki/Set_packing" title="Set packing">Set</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Circle_packing" title="Circle packing">Circle packing</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Circle_packing_in_a_circle" title="Circle packing in a circle">In a circle</a> / <a href="/wiki/Circle_packing_in_an_equilateral_triangle" title="Circle packing in an equilateral triangle">equilateral triangle</a> / <a href="/wiki/Circle_packing_in_an_isosceles_right_triangle" title="Circle packing in an isosceles right triangle">isosceles right triangle</a> / <a href="/wiki/Circle_packing_in_a_square" title="Circle packing in a square">square</a></li> <li><a href="/wiki/Apollonian_gasket" title="Apollonian gasket">Apollonian gasket</a></li> <li><a href="/wiki/Circle_packing_theorem" title="Circle packing theorem">Circle packing theorem</a></li> <li><a href="/wiki/Tammes_problem" title="Tammes problem">Tammes problem <span style="font-size:85%;">(on sphere)</span></a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Sphere_packing" title="Sphere packing">Sphere packing</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Apollonian_sphere_packing" title="Apollonian sphere packing">Apollonian</a></li> <li><a href="/wiki/Finite_sphere_packing" title="Finite sphere packing">Finite</a></li> <li><a href="/wiki/Sphere_packing_in_a_sphere" title="Sphere packing in a sphere">In a sphere</a></li> <li><a href="/wiki/Sphere_packing_in_a_cube" title="Sphere packing in a cube">In a cube</a></li> <li><a href="/wiki/Sphere_packing_in_a_cylinder" title="Sphere packing in a cylinder"> In a cylinder</a></li> <li><a href="/wiki/Close-packing_of_equal_spheres" title="Close-packing of equal spheres">Close-packing</a></li> <li><a href="/wiki/Kissing_number" title="Kissing number">Kissing number</a></li> <li><a href="/wiki/Hamming_bound" title="Hamming bound">Sphere-packing (Hamming) bound</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other 2-D packing</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Square_packing" title="Square packing">Square packing</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other 3-D packing</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Tetrahedron_packing" title="Tetrahedron packing">Tetrahedron</a></li> <li><a href="/wiki/Ellipsoid_packing" title="Ellipsoid packing">Ellipsoid</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Puzzles</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Conway_puzzle" title="Conway puzzle">Conway</a></li> <li><a href="/wiki/Slothouber%E2%80%93Graatsma_puzzle" title="Slothouber–Graatsma puzzle">Slothouber–Graatsma</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Packing_problems&oldid=1236278829">https://en.wikipedia.org/w/index.php?title=Packing_problems&oldid=1236278829</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Packing_problems" title="Category:Packing problems">Packing problems</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Commons_category_link_from_Wikidata" title="Category:Commons category link from Wikidata">Commons category link from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_September_2019" title="Category:Use dmy dates from September 2019">Use dmy dates from September 2019</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 23 July 2024, at 21:01<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Packing_problems&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-rbglq","wgBackendResponseTime":131,"wgPageParseReport":{"limitreport":{"cputime":"0.531","walltime":"0.771","ppvisitednodes":{"value":2985,"limit":1000000},"postexpandincludesize":{"value":90036,"limit":2097152},"templateargumentsize":{"value":2535,"limit":2097152},"expansiondepth":{"value":14,"limit":100},"expensivefunctioncount":{"value":10,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":121064,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 579.322 1 -total"," 31.98% 185.283 1 Template:Reflist"," 23.21% 134.481 12 Template:Cite_journal"," 16.01% 92.727 2 Template:Sidebar"," 15.46% 89.557 1 Template:Covering/packing-problem_pairs"," 11.66% 67.574 1 Template:Short_description"," 8.53% 49.436 1 Template:Commons_category"," 8.21% 47.577 1 Template:Sister_project"," 7.94% 46.005 1 Template:Side_box"," 7.60% 44.047 2 Template:Pagetype"]},"scribunto":{"limitreport-timeusage":{"value":"0.309","limit":"10.000"},"limitreport-memusage":{"value":5915787,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-5dc468848-ltmh5","timestamp":"20241122140518","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Packing problems","url":"https:\/\/en.wikipedia.org\/wiki\/Packing_problems","sameAs":"http:\/\/www.wikidata.org\/entity\/Q3851477","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q3851477","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-04-19T20:18:23Z","dateModified":"2024-07-23T21:01:58Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/2\/26\/Seissand.png","headline":"class of optimization problems in mathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible"}</script> </body> </html>