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:
https://lup.lub.lu.se/record/7422623
- author
- Floderus, Peter
LU
; Jansson, Jesper
; Levcopoulos, Christos
LU
; Lingas, Andrzej
LU
and Sledneu, Dzmitry
LU
- organization
- publishing date
- 2014
- 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
- 0302-9743
- 1611-3349
- 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
- 2016-04-01 10:58:45
- date last changed
- 2025-01-14 03:35:11
@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}},
booktitle = {{Algorithms and Computation, ISAAC 2014}},
isbn = {{978-3-319-13074-3}},
issn = {{0302-9743}},
keywords = {{Geometric decompositions; Minimum number rectangulation; Polyhedron; Matrix multiplication; Time complexity}},
language = {{eng}},
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}},
doi = {{10.1007/978-3-319-13075-0_6}},
volume = {{8889}},
year = {{2014}},
}