3D rectangulations and geometric matrix multiplication

Peter Floderus, Jesper Andreas Jansson, Christos Levcopoulos, Andrzej Lingas, Dzmitry Sledneu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

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(mlogm) time, where m is the number of corners in P. We then apply it to 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 Õ(n2+min{rArB, n min{rA, rB}}) time, where Õ suppresses polylogarithmic (in n) factors and where rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
Original languageEnglish
Title of host publicationAlgorithms and Computation - 25th International Symposium, ISAAC 2014, Proceedings
EditorsHee-Kap Ahn, Chan-Su Shin
Pages65-78
Number of pages14
ISBN (Electronic)9783319130743
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event25th International Symposium on Algorithms and Computation, ISAAC 2014 - Jeonju, Korea, Republic of
Duration: 15 Dec 201417 Dec 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
VolumeLNCS 8889
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Symposium on Algorithms and Computation, ISAAC 2014
CountryKorea, Republic of
CityJeonju
Period15/12/1417/12/14

Keywords

  • Geometric decompositions
  • Matrix multiplication
  • Minimum number rectangulation
  • Polyhedron
  • Time complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this