3D Rectangulations and Geometric Matrix Multiplication
(2018) In Algorithmica 80(1). p.136154 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
 201801
 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
 14320541
 DOI
 10.1007/s0045301602473
 language
 English
 LU publication?
 yes
 id
 619ce54bf063406eaa3ef8d4cbe1d825
 date added to LUP
 20161118 09:26:31
 date last changed
 20180529 11:07:23
@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}, number = {1}, pages = {136154}, publisher = {Springer}, series = {Algorithmica}, title = {3D Rectangulations and Geometric Matrix Multiplication}, url = {http://dx.doi.org/10.1007/s0045301602473}, volume = {80}, year = {2018}, }