TY - GEN

T1 - 3D rectangulations and geometric matrix multiplication

AU - Floderus, Peter

AU - Jansson, Jesper Andreas

AU - Levcopoulos, Christos

AU - Lingas, Andrzej

AU - Sledneu, Dzmitry

PY - 2014/1/1

Y1 - 2014/1/1

N2 - The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case 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 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 Õ(n2+min{rArB, n min{rA, rB}}) time, where Õ suppresses polylogarithmic (in n) factors and where rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.

AB - The problem of partitioning an input rectilinear polyhedron P into a minimum number of 3D rectangles is known to be NP-hard. We first develop a 4-approximation algorithm for the special case 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 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 Õ(n2+min{rArB, n min{rA, rB}}) time, where Õ suppresses polylogarithmic (in n) factors and where rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.

KW - Geometric decompositions

KW - Matrix multiplication

KW - Minimum number rectangulation

KW - Polyhedron

KW - Time complexity

UR - http://www.scopus.com/inward/record.url?scp=84921641440&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13075-0_6

DO - 10.1007/978-3-319-13075-0_6

M3 - Conference article published in proceeding or book

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 65

EP - 78

BT - Algorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings

A2 - Ahn, Hee-Kap

A2 - Shin, Chan-Su

T2 - 25th International Symposium on Algorithms and Computation, ISAAC 2014

Y2 - 15 December 2014 through 17 December 2014

ER -