Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing Article Swipe
Jian‐Rong Zhou
,
Jiyao He
,
Kun He
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2403.06211
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2403.06211
The problem of packing unequal circles into a circular container stands as a classic and challenging optimization problem in computational geometry. This study introduces a suite of innovative and efficient methods to tackle this problem. Firstly, we present a novel layout-graph transformation method that represents configurations as graphs, together with an inexact hash method facilitating fast comparison of configurations for isomorphism or similarity. Leveraging these advancements, we propose an Iterative Solution-Hashing Search algorithm adept at circumventing redundant exploration through efficient configuration recording. Additionally, we introduce several enhancements to refine the optimization and search processes, including an adaptive adjacency maintenance method, an efficient vacancy detection technique, and a Voronoi-based locating method. Through comprehensive computational experiments across various benchmark instances, our algorithm demonstrates superior performance over existing state-of-the-art methods, showcasing remarkable applicability and versatility. Notably, our algorithm surpasses the best-known results for 56 out of 179 benchmark instances while achieving parity with the remaining instances.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2403.06211
- https://arxiv.org/pdf/2403.06211
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4392737311
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4392737311Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2403.06211Digital Object Identifier
- Title
-
Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle PackingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-03-10Full publication date if available
- Authors
-
Jian‐Rong Zhou, Jiyao He, Kun HeList of authors in order
- Landing page
-
https://arxiv.org/abs/2403.06211Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2403.06211Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2403.06211Direct OA link when available
- Concepts
-
Transformation (genetics), Graph, Computer science, Theoretical computer science, Mathematics, Biochemistry, Chemistry, GeneTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4392737311 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2403.06211 |
| ids.doi | https://doi.org/10.48550/arxiv.2403.06211 |
| ids.openalex | https://openalex.org/W4392737311 |
| fwci | |
| type | preprint |
| title | Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12176 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9965999722480774 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2209 |
| topics[0].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[0].display_name | Optimization and Packing Problems |
| topics[1].id | https://openalex.org/T11814 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9812999963760376 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2209 |
| topics[1].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[1].display_name | Advanced Manufacturing and Logistics Optimization |
| topics[2].id | https://openalex.org/T11159 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9383000135421753 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2209 |
| topics[2].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[2].display_name | Manufacturing Process and Optimization |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C204241405 |
| concepts[0].level | 3 |
| concepts[0].score | 0.5894726514816284 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q461499 |
| concepts[0].display_name | Transformation (genetics) |
| concepts[1].id | https://openalex.org/C132525143 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5698220133781433 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[1].display_name | Graph |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5215025544166565 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C80444323 |
| concepts[3].level | 1 |
| concepts[3].score | 0.43156710267066956 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[3].display_name | Theoretical computer science |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.33801376819610596 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| concepts[5].id | https://openalex.org/C55493867 |
| concepts[5].level | 1 |
| concepts[5].score | 0.0 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[5].display_name | Biochemistry |
| concepts[6].id | https://openalex.org/C185592680 |
| concepts[6].level | 0 |
| concepts[6].score | 0.0 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2329 |
| concepts[6].display_name | Chemistry |
| concepts[7].id | https://openalex.org/C104317684 |
| concepts[7].level | 2 |
| concepts[7].score | 0.0 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[7].display_name | Gene |
| keywords[0].id | https://openalex.org/keywords/transformation |
| keywords[0].score | 0.5894726514816284 |
| keywords[0].display_name | Transformation (genetics) |
| keywords[1].id | https://openalex.org/keywords/graph |
| keywords[1].score | 0.5698220133781433 |
| keywords[1].display_name | Graph |
| keywords[2].id | https://openalex.org/keywords/computer-science |
| keywords[2].score | 0.5215025544166565 |
| keywords[2].display_name | Computer science |
| keywords[3].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[3].score | 0.43156710267066956 |
| keywords[3].display_name | Theoretical computer science |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.33801376819610596 |
| keywords[4].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2403.06211 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2403.06211 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2403.06211 |
| locations[1].id | doi:10.48550/arxiv.2403.06211 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2403.06211 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5110363713 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Jian‐Rong Zhou |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Zhou, Jianrong |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5102628821 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Jiyao He |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | He, Jiyao |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5100700363 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-8943-8671 |
| authorships[2].author.display_name | Kun He |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | He, Kun |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2403.06211 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-03-13T00:00:00 |
| display_name | Solution-Hashing Search Based on Layout-Graph Transformation for Unequal Circle Packing |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12176 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9965999722480774 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2209 |
| primary_topic.subfield.display_name | Industrial and Manufacturing Engineering |
| primary_topic.display_name | Optimization and Packing Problems |
| related_works | https://openalex.org/W2748952813, https://openalex.org/W1979597421, https://openalex.org/W2007980826, https://openalex.org/W2061531152, https://openalex.org/W3002753104, https://openalex.org/W2077600819, https://openalex.org/W2142036596, https://openalex.org/W2072657027, https://openalex.org/W2600246793, https://openalex.org/W4238204885 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2403.06211 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2403.06211 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2403.06211 |
| primary_location.id | pmh:oai:arXiv.org:2403.06211 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2403.06211 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2403.06211 |
| publication_date | 2024-03-10 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 7, 12, 24, 38, 106 |
| abstract_inverted_index.56 | 140 |
| abstract_inverted_index.an | 50, 68, 95, 100 |
| abstract_inverted_index.as | 11, 46 |
| abstract_inverted_index.at | 74 |
| abstract_inverted_index.in | 18 |
| abstract_inverted_index.of | 2, 26, 57, 142 |
| abstract_inverted_index.or | 61 |
| abstract_inverted_index.to | 31, 87 |
| abstract_inverted_index.we | 36, 66, 83 |
| abstract_inverted_index.179 | 143 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 14, 28, 91, 105, 130 |
| abstract_inverted_index.for | 59, 139 |
| abstract_inverted_index.our | 118, 133 |
| abstract_inverted_index.out | 141 |
| abstract_inverted_index.the | 89, 136, 150 |
| abstract_inverted_index.This | 21 |
| abstract_inverted_index.fast | 55 |
| abstract_inverted_index.hash | 52 |
| abstract_inverted_index.into | 6 |
| abstract_inverted_index.over | 123 |
| abstract_inverted_index.that | 43 |
| abstract_inverted_index.this | 33 |
| abstract_inverted_index.with | 49, 149 |
| abstract_inverted_index.adept | 73 |
| abstract_inverted_index.novel | 39 |
| abstract_inverted_index.study | 22 |
| abstract_inverted_index.suite | 25 |
| abstract_inverted_index.these | 64 |
| abstract_inverted_index.while | 146 |
| abstract_inverted_index.Search | 71 |
| abstract_inverted_index.across | 114 |
| abstract_inverted_index.method | 42, 53 |
| abstract_inverted_index.parity | 148 |
| abstract_inverted_index.refine | 88 |
| abstract_inverted_index.search | 92 |
| abstract_inverted_index.stands | 10 |
| abstract_inverted_index.tackle | 32 |
| abstract_inverted_index.Through | 110 |
| abstract_inverted_index.circles | 5 |
| abstract_inverted_index.classic | 13 |
| abstract_inverted_index.graphs, | 47 |
| abstract_inverted_index.inexact | 51 |
| abstract_inverted_index.method, | 99 |
| abstract_inverted_index.method. | 109 |
| abstract_inverted_index.methods | 30 |
| abstract_inverted_index.packing | 3 |
| abstract_inverted_index.present | 37 |
| abstract_inverted_index.problem | 1, 17 |
| abstract_inverted_index.propose | 67 |
| abstract_inverted_index.results | 138 |
| abstract_inverted_index.several | 85 |
| abstract_inverted_index.through | 78 |
| abstract_inverted_index.unequal | 4 |
| abstract_inverted_index.vacancy | 102 |
| abstract_inverted_index.various | 115 |
| abstract_inverted_index.Firstly, | 35 |
| abstract_inverted_index.Notably, | 132 |
| abstract_inverted_index.adaptive | 96 |
| abstract_inverted_index.circular | 8 |
| abstract_inverted_index.existing | 124 |
| abstract_inverted_index.locating | 108 |
| abstract_inverted_index.methods, | 126 |
| abstract_inverted_index.problem. | 34 |
| abstract_inverted_index.superior | 121 |
| abstract_inverted_index.together | 48 |
| abstract_inverted_index.Iterative | 69 |
| abstract_inverted_index.achieving | 147 |
| abstract_inverted_index.adjacency | 97 |
| abstract_inverted_index.algorithm | 72, 119, 134 |
| abstract_inverted_index.benchmark | 116, 144 |
| abstract_inverted_index.container | 9 |
| abstract_inverted_index.detection | 103 |
| abstract_inverted_index.efficient | 29, 79, 101 |
| abstract_inverted_index.geometry. | 20 |
| abstract_inverted_index.including | 94 |
| abstract_inverted_index.instances | 145 |
| abstract_inverted_index.introduce | 84 |
| abstract_inverted_index.redundant | 76 |
| abstract_inverted_index.remaining | 151 |
| abstract_inverted_index.surpasses | 135 |
| abstract_inverted_index.Leveraging | 63 |
| abstract_inverted_index.best-known | 137 |
| abstract_inverted_index.comparison | 56 |
| abstract_inverted_index.innovative | 27 |
| abstract_inverted_index.instances, | 117 |
| abstract_inverted_index.instances. | 152 |
| abstract_inverted_index.introduces | 23 |
| abstract_inverted_index.processes, | 93 |
| abstract_inverted_index.recording. | 81 |
| abstract_inverted_index.remarkable | 128 |
| abstract_inverted_index.represents | 44 |
| abstract_inverted_index.showcasing | 127 |
| abstract_inverted_index.technique, | 104 |
| abstract_inverted_index.challenging | 15 |
| abstract_inverted_index.experiments | 113 |
| abstract_inverted_index.exploration | 77 |
| abstract_inverted_index.isomorphism | 60 |
| abstract_inverted_index.maintenance | 98 |
| abstract_inverted_index.performance | 122 |
| abstract_inverted_index.similarity. | 62 |
| abstract_inverted_index.demonstrates | 120 |
| abstract_inverted_index.enhancements | 86 |
| abstract_inverted_index.facilitating | 54 |
| abstract_inverted_index.layout-graph | 40 |
| abstract_inverted_index.optimization | 16, 90 |
| abstract_inverted_index.versatility. | 131 |
| abstract_inverted_index.Additionally, | 82 |
| abstract_inverted_index.Voronoi-based | 107 |
| abstract_inverted_index.advancements, | 65 |
| abstract_inverted_index.applicability | 129 |
| abstract_inverted_index.circumventing | 75 |
| abstract_inverted_index.comprehensive | 111 |
| abstract_inverted_index.computational | 19, 112 |
| abstract_inverted_index.configuration | 80 |
| abstract_inverted_index.configurations | 45, 58 |
| abstract_inverted_index.transformation | 41 |
| abstract_inverted_index.Solution-Hashing | 70 |
| abstract_inverted_index.state-of-the-art | 125 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |