3D Rectangulations and Geometric Matrix Multiplication

Forskningsoutput: TidskriftsbidragArtikel i vetenskaplig tidskrift

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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Kyoto University
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)

Nyckelord

Originalspråkengelska
Sidor (från-till)136-154
TidskriftAlgorithmica
Volym80
Utgåva nummer1
Tidigt onlinedatum2016 nov 16
StatusPublished - 2018 jan
PublikationskategoriForskning
Peer review utfördJa