3D Rectangulations and Geometric Matrix Multiplication

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)

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(mlog m) 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 rAand rBdenote the minimum number of 3D rectangles into which the 3D histograms induced by A and B can be partitioned, respectively.
Original languageEnglish
Pages (from-to)136-154
Number of pages19
JournalAlgorithmica
Volume80
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes

Keywords

  • Decomposition problem
  • Matrix multiplication
  • Minimum rectangulation
  • Orthogonal polyhedron
  • Time complexity

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this