Advanced

3D Rectangulations and Geometric Matrix Multiplication

SAVONEN FLODERUS, PETER LU ; Jansson, Jesper; Levcopoulos, Christos LU ; Lingas, Andrzej LU and SLEDNEU, DZMITRY LU (2018) In Algorithmica 80(1). p.136-154
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
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
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
2018-05-29 11:07:23
@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},
  number       = {1},
  pages        = {136--154},
  publisher    = {Springer},
  series       = {Algorithmica},
  title        = {3D Rectangulations and Geometric Matrix Multiplication},
  url          = {http://dx.doi.org/10.1007/s00453-016-0247-3},
  volume       = {80},
  year         = {2018},
}