Advanced

3D Rectangulations and Geometric Matrix Multiplication

SAVONEN FLODERUS, PETER LU ; Jansson, Jesper; Levcopoulos, Christos LU ; Lingas, Andrzej LU and SLEDNEU, DZMITRY LU (2016) In Algorithmica
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:
author
organization
publishing date
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
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
2017-05-05 13:44:28
@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},
  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/s00453-016-0247-3},
  year         = {2016},
}