3D Rectangulations and Geometric Matrix Multiplication
(2018) In Algorithmica 80(1). p.136-154- Abstract
- The problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. In this paper, we first develop a 4-approximation algorithm for the special case of the problem in which P is a 3D histogram. It runs in O(mlogm) time, where m is the number of corners in P. We then apply it to exactly compute the arithmetic matrix product of two n×n matrices A and B with nonnegative integer entries, yielding a method for computing A×B in O~(n2+min{rArB,nmin{rA, rB}}) time, where O~ suppresses polylogarithmic (in n) factors and where rA and rB denote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/619ce54b-f063-406e-aa3e-f8d4cbe1d825
- author
- SAVONEN FLODERUS, PETER LU ; Jansson, Jesper ; Levcopoulos, Christos LU ; Lingas, Andrzej LU and SLEDNEU, DZMITRY LU
- organization
- publishing date
- 2018-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Decomposition problem, Minimum rectangulation, Orthogonal polyhedron, Matrix multiplication, Time Complexity
- in
- Algorithmica
- volume
- 80
- issue
- 1
- pages
- 136 - 154
- publisher
- Springer
- external identifiers
-
- scopus:84995503471
- ISSN
- 1432-0541
- DOI
- 10.1007/s00453-016-0247-3
- language
- English
- LU publication?
- yes
- id
- 619ce54b-f063-406e-aa3e-f8d4cbe1d825
- date added to LUP
- 2016-11-18 09:26:31
- date last changed
- 2022-03-08 22:21:25
@article{619ce54b-f063-406e-aa3e-f8d4cbe1d825, abstract = {{The problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. In this paper, we first develop a 4-approximation algorithm for the special case of the problem in which P is a 3D histogram. It runs in O(mlogm) time, where m is the number of corners in P. We then apply it to exactly compute the arithmetic matrix product of two n×n matrices A and B with nonnegative integer entries, yielding a method for computing A×B in O~(n2+min{rArB,nmin{rA, rB}}) time, where O~ suppresses polylogarithmic (in n) factors and where rA and rB denote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.}}, author = {{SAVONEN FLODERUS, PETER and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and SLEDNEU, DZMITRY}}, issn = {{1432-0541}}, keywords = {{Decomposition problem; Minimum rectangulation; Orthogonal polyhedron; Matrix multiplication; Time Complexity}}, language = {{eng}}, number = {{1}}, pages = {{136--154}}, publisher = {{Springer}}, series = {{Algorithmica}}, title = {{3D Rectangulations and Geometric Matrix Multiplication}}, url = {{http://dx.doi.org/10.1007/s00453-016-0247-3}}, doi = {{10.1007/s00453-016-0247-3}}, volume = {{80}}, year = {{2018}}, }