3D Rectangulations and Geometric Matrix Multiplication
(2016) In Algorithmica Abstract
 The problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles is known to be NPhard. In this paper, we first develop a 4approximation 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:
http://lup.lub.lu.se/record/619ce54bf063406eaa3ef8d4cbe1d825
 author
 SAVONEN FLODERUS, PETER ^{LU} ; Jansson, Jesper; Levcopoulos, Christos ^{LU} ; Lingas, Andrzej ^{LU} and SLEDNEU, DZMITRY ^{LU}
 organization
 publishing date
 20161116
 type
 Contribution to journal
 publication status
 epub
 subject
 keywords
 Decomposition problem, Minimum rectangulation, Orthogonal polyhedron, Matrix multiplication, Time Complexity
 in
 Algorithmica
 pages
 19 pages
 publisher
 Springer
 external identifiers

 scopus:84995503471
 ISSN
 14320541
 DOI
 10.1007/s0045301602473
 language
 English
 LU publication?
 yes
 id
 619ce54bf063406eaa3ef8d4cbe1d825
 date added to LUP
 20161118 09:26:31
 date last changed
 20170505 13:44:28
@article{619ce54bf063406eaa3ef8d4cbe1d825, abstract = {The problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles is known to be NPhard. In this paper, we first develop a 4approximation 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 = {14320541}, keyword = {Decomposition problem,Minimum rectangulation,Orthogonal polyhedron,Matrix multiplication,Time Complexity}, language = {eng}, month = {11}, pages = {19}, publisher = {Springer}, series = {Algorithmica}, title = {3D Rectangulations and Geometric Matrix Multiplication}, url = {http://dx.doi.org/10.1007/s0045301602473}, year = {2016}, }