3D Rectangulations and Geometric Matrix Multiplication
(2014) 25th International Symposium on Algorithms and Computation (ISAAC), 2014 In Algorithms and Computation, ISAAC 2014 8889. p.6578 Abstract
 The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NPhard. We first develop a 4approximation algorithm for the special case in which P is a 3D histogram. It runs in O(m log m) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n x n matrices A and B with nonnegative integer entries, yielding a method for computing A x B in (O) over tilde (n(2) + min{rArB, n min{rA, rB}}) time, where (O) over tilde 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/7422623
 author
 Floderus, Peter ^{LU} ; Jansson, Jesper; Levcopoulos, Christos ^{LU} ; Lingas, Andrzej ^{LU} and Sledneu, Dzmitry ^{LU}
 organization
 publishing date
 2014
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Geometric decompositions, Minimum number rectangulation, Polyhedron, Matrix multiplication, Time complexity
 in
 Algorithms and Computation, ISAAC 2014
 volume
 8889
 pages
 65  78
 publisher
 Springer
 conference name
 25th International Symposium on Algorithms and Computation (ISAAC), 2014
 external identifiers

 wos:000354865900006
 scopus:84921641440
 ISSN
 16113349
 03029743
 ISBN
 9783319130743
 DOI
 10.1007/9783319130750_6
 language
 English
 LU publication?
 yes
 id
 2eb0289555df4b628adc28a2da61f448 (old id 7422623)
 date added to LUP
 20150626 11:45:54
 date last changed
 20180107 04:40:00
@inproceedings{2eb0289555df4b628adc28a2da61f448, abstract = {The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NPhard. We first develop a 4approximation algorithm for the special case in which P is a 3D histogram. It runs in O(m log m) time, where m is the number of corners in P. We then apply it to compute the arithmetic matrix product of two n x n matrices A and B with nonnegative integer entries, yielding a method for computing A x B in (O) over tilde (n(2) + min{rArB, n min{rA, rB}}) time, where (O) over tilde 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 = {Floderus, Peter and Jansson, Jesper and Levcopoulos, Christos and Lingas, Andrzej and Sledneu, Dzmitry}, booktitle = {Algorithms and Computation, ISAAC 2014}, isbn = {9783319130743}, issn = {16113349}, keyword = {Geometric decompositions,Minimum number rectangulation,Polyhedron,Matrix multiplication,Time complexity}, language = {eng}, pages = {6578}, publisher = {Springer}, title = {3D Rectangulations and Geometric Matrix Multiplication}, url = {http://dx.doi.org/10.1007/9783319130750_6}, volume = {8889}, year = {2014}, }