Geometry and complexity of O'Hara's algorithm
In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara&#...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2009-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2692/pdf |
| _version_ | 1797270339215949824 |
|---|---|
| author | Matjaž Konvalinka Igor Pak |
| author_facet | Matjaž Konvalinka Igor Pak |
| author_sort | Matjaž Konvalinka |
| collection | DOAJ |
| description | In this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara's bijection is efficient in most cases and mildly exponential in general. Finally, we see that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction. |
| first_indexed | 2024-04-25T02:02:42Z |
| format | Article |
| id | doaj.art-375a016d1e624f4a96f5e23fa5b4a0ef |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:42Z |
| publishDate | 2009-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-375a016d1e624f4a96f5e23fa5b4a0ef2024-03-07T14:45:40ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502009-01-01DMTCS Proceedings vol. AK,...Proceedings10.46298/dmtcs.26922692Geometry and complexity of O'Hara's algorithmMatjaž Konvalinka0https://orcid.org/0000-0002-0739-6744Igor Pak1Department of Mathematics, Vanderbilt UniversitySchool of MathematicsIn this paper we analyze O'Hara's partition bijection. We present three type of results. First, we see that O'Hara's bijection can be viewed geometrically as a certain scissor congruence type result. Second, we present a number of new complexity bounds, proving that O'Hara's bijection is efficient in most cases and mildly exponential in general. Finally, we see that for identities with finite support, the map of the O'Hara's bijection can be computed in polynomial time, i.e. much more efficiently than by O'Hara's construction.https://dmtcs.episciences.org/2692/pdfpartitionso'hara's algorithmcomplexity[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Matjaž Konvalinka Igor Pak Geometry and complexity of O'Hara's algorithm Discrete Mathematics & Theoretical Computer Science partitions o'hara's algorithm complexity [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Geometry and complexity of O'Hara's algorithm |
| title_full | Geometry and complexity of O'Hara's algorithm |
| title_fullStr | Geometry and complexity of O'Hara's algorithm |
| title_full_unstemmed | Geometry and complexity of O'Hara's algorithm |
| title_short | Geometry and complexity of O'Hara's algorithm |
| title_sort | geometry and complexity of o hara s algorithm |
| topic | partitions o'hara's algorithm complexity [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2692/pdf |
| work_keys_str_mv | AT matjazkonvalinka geometryandcomplexityofoharasalgorithm AT igorpak geometryandcomplexityofoharasalgorithm |