Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

3D Rectangulations and Geometric Matrix Multiplication

SAVONEN FLODERUS, PETER LU ; Jansson, Jesper ; Levcopoulos, Christos LU orcid ; 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
; ; ; and
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
2022-03-08 22:21:25
@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}},
  keywords     = {{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}},
  doi          = {{10.1007/s00453-016-0247-3}},
  volume       = {{80}},
  year         = {{2018}},
}