An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D Article Swipe
Pankaj K. Agarwal
,
Alex Steiger
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icalp.2021.10
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.icalp.2021.10
Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ³. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n²). We show that U can be computed in O(n log³ n + κ) time if C is in general position. The algorithm also computes the union of a set of fat boxes (i.e., boxes with bounded aspect ratio) within the same time bound. If the cubes in C are congruent or have bounded depth, the running time improves to O(n log² n), and if both conditions hold, the running time improves to O(n log n).
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10
- OA Status
- green
- Related Works
- 1
- OpenAlex ID
- https://openalex.org/W3186975215
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3186975215Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.icalp.2021.10Digital Object Identifier
- Title
-
An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3DWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-01-01Full publication date if available
- Authors
-
Pankaj K. Agarwal, Alex SteigerList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10Direct OA link when available
- Concepts
-
Computer science, AlgorithmTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
1Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3186975215 |
|---|---|
| doi | https://doi.org/10.4230/lipics.icalp.2021.10 |
| ids.doi | https://doi.org/10.4230/lipics.icalp.2021.10 |
| ids.mag | 3186975215 |
| ids.openalex | https://openalex.org/W3186975215 |
| fwci | 0.0 |
| type | article |
| title | An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11159 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9466000199317932 |
| 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 | Manufacturing Process and Optimization |
| topics[1].id | https://openalex.org/T14339 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9217000007629395 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Image Processing and 3D Reconstruction |
| topics[2].id | https://openalex.org/T10783 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9056000113487244 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2203 |
| topics[2].subfield.display_name | Automotive Engineering |
| topics[2].display_name | Additive Manufacturing and 3D Printing Technologies |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.5885037183761597 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C11413529 |
| concepts[1].level | 1 |
| concepts[1].score | 0.3787536919116974 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[1].display_name | Algorithm |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.5885037183761597 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/algorithm |
| keywords[1].score | 0.3787536919116974 |
| keywords[1].display_name | Algorithm |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:14079 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10 |
| locations[1].id | doi:10.4230/lipics.icalp.2021.10 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S7407052059 |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | Dagstuhl Research Online Publication Server |
| locations[1].source.host_organization | |
| locations[1].source.host_organization_name | |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | |
| 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.4230/lipics.icalp.2021.10 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A5058649592 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-9439-181X |
| authorships[0].author.display_name | Pankaj K. Agarwal |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I170897317 |
| authorships[0].affiliations[0].raw_affiliation_string | Duke University, Durham, United States |
| authorships[0].institutions[0].id | https://openalex.org/I170897317 |
| authorships[0].institutions[0].ror | https://ror.org/00py81415 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I170897317 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | Duke University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Pankaj K. Agarwal |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Duke University, Durham, United States |
| authorships[1].author.id | https://openalex.org/A5061138887 |
| authorships[1].author.orcid | https://orcid.org/0000-0003-1546-6244 |
| authorships[1].author.display_name | Alex Steiger |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I170897317 |
| authorships[1].affiliations[0].raw_affiliation_string | Duke University, Durham, United States |
| authorships[1].institutions[0].id | https://openalex.org/I170897317 |
| authorships[1].institutions[0].ror | https://ror.org/00py81415 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I170897317 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | Duke University |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Alex Steiger |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Duke University, Durham, United States |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2021-08-02T00:00:00 |
| display_name | An Output-Sensitive Algorithm for Computing the Union of Cubes and Fat Boxes in 3D |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11159 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9466000199317932 |
| 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 | Manufacturing Process and Optimization |
| related_works | https://openalex.org/W2167642885 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:14079 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| 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 | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:14079 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.10 |
| publication_date | 2021-01-01 |
| publication_year | 2021 |
| referenced_works_count | 0 |
| abstract_inverted_index.+ | 47 |
| abstract_inverted_index.C | 1, 51, 83 |
| abstract_inverted_index.U | 15, 39 |
| abstract_inverted_index.a | 3, 63 |
| abstract_inverted_index.n | 6, 46 |
| abstract_inverted_index.If | 79 |
| abstract_inverted_index.We | 36 |
| abstract_inverted_index.be | 2, 16, 22, 41 |
| abstract_inverted_index.if | 50, 99 |
| abstract_inverted_index.in | 12, 43, 53, 82 |
| abstract_inverted_index.is | 52 |
| abstract_inverted_index.of | 5, 9, 25, 62, 65 |
| abstract_inverted_index.on | 27 |
| abstract_inverted_index.or | 86 |
| abstract_inverted_index.to | 94, 107 |
| abstract_inverted_index.κ | 21, 29 |
| abstract_inverted_index.Let | 0, 14 |
| abstract_inverted_index.O(n | 44, 95, 108 |
| abstract_inverted_index.The | 56 |
| abstract_inverted_index.and | 19, 34, 98 |
| abstract_inverted_index.are | 84 |
| abstract_inverted_index.can | 30, 40 |
| abstract_inverted_index.fat | 66 |
| abstract_inverted_index.let | 20 |
| abstract_inverted_index.log | 109 |
| abstract_inverted_index.n), | 97 |
| abstract_inverted_index.n). | 110 |
| abstract_inverted_index.set | 4, 64 |
| abstract_inverted_index.the | 23, 60, 75, 80, 90, 103 |
| abstract_inverted_index.κ) | 48 |
| abstract_inverted_index.O(1) | 33 |
| abstract_inverted_index.also | 58 |
| abstract_inverted_index.both | 100 |
| abstract_inverted_index.have | 87 |
| abstract_inverted_index.same | 76 |
| abstract_inverted_index.show | 37 |
| abstract_inverted_index.that | 38 |
| abstract_inverted_index.time | 49, 77, 92, 105 |
| abstract_inverted_index.vary | 31 |
| abstract_inverted_index.with | 70 |
| abstract_inverted_index.boxes | 67, 69 |
| abstract_inverted_index.cubes | 8, 81 |
| abstract_inverted_index.hold, | 102 |
| abstract_inverted_index.log² | 96 |
| abstract_inverted_index.log³ | 45 |
| abstract_inverted_index.sizes | 11 |
| abstract_inverted_index.their | 17 |
| abstract_inverted_index.union | 61 |
| abstract_inverted_index.∂U; | 28 |
| abstract_inverted_index.(i.e., | 68 |
| abstract_inverted_index.aspect | 72 |
| abstract_inverted_index.bound. | 78 |
| abstract_inverted_index.depth, | 89 |
| abstract_inverted_index.number | 24 |
| abstract_inverted_index.ratio) | 73 |
| abstract_inverted_index.union, | 18 |
| abstract_inverted_index.within | 74 |
| abstract_inverted_index.ℝ³. | 13 |
| abstract_inverted_index.O(n²). | 35 |
| abstract_inverted_index.between | 32 |
| abstract_inverted_index.bounded | 71, 88 |
| abstract_inverted_index.general | 54 |
| abstract_inverted_index.running | 91, 104 |
| abstract_inverted_index.computed | 42 |
| abstract_inverted_index.computes | 59 |
| abstract_inverted_index.improves | 93, 106 |
| abstract_inverted_index.vertices | 26 |
| abstract_inverted_index.algorithm | 57 |
| abstract_inverted_index.arbitrary | 10 |
| abstract_inverted_index.congruent | 85 |
| abstract_inverted_index.position. | 55 |
| abstract_inverted_index.conditions | 101 |
| abstract_inverted_index.axis-aligned | 7 |
| cited_by_percentile_year | |
| countries_distinct_count | 1 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile.value | 0.12627454 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |