Advanced

3D Rectangulations and Geometric Matrix Multiplication

Floderus, Peter LU ; Jansson, Jesper; Levcopoulos, Christos LU ; Lingas, Andrzej LU and Sledneu, Dzmitry LU (2014) 25th International Symposium on Algorithms and Computation (ISAAC), 2014 8889. p.65-78
Abstract
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(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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Geometric decompositions, Minimum number rectangulation, Polyhedron, Matrix multiplication, Time complexity
host publication
Algorithms and Computation, ISAAC 2014
volume
8889
pages
65 - 78
publisher
Springer
conference name
25th International Symposium on Algorithms and Computation (ISAAC), 2014
conference location
Jeonju, Korea, Republic of
conference dates
2014-12-15 - 2014-12-17
external identifiers
  • wos:000354865900006
  • scopus:84921641440
ISSN
1611-3349
0302-9743
ISBN
978-3-319-13074-3
DOI
10.1007/978-3-319-13075-0_6
language
English
LU publication?
yes
id
2eb02895-55df-4b62-8adc-28a2da61f448 (old id 7422623)
date added to LUP
2015-06-26 11:45:54
date last changed
2019-02-20 02:59:53
@inproceedings{2eb02895-55df-4b62-8adc-28a2da61f448,
  abstract     = {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(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},
  isbn         = {978-3-319-13074-3},
  issn         = {1611-3349},
  keyword      = {Geometric decompositions,Minimum number rectangulation,Polyhedron,Matrix multiplication,Time complexity},
  language     = {eng},
  location     = {Jeonju, Korea, Republic of},
  pages        = {65--78},
  publisher    = {Springer},
  title        = {3D Rectangulations and Geometric Matrix Multiplication},
  url          = {http://dx.doi.org/10.1007/978-3-319-13075-0_6},
  volume       = {8889},
  year         = {2014},
}