Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

3D Rectangulations and Geometric Matrix Multiplication

In English

Författare

Summary, in English

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.

Publiceringsår

2014

Språk

Engelska

Sidor

65-78

Publikation/Tidskrift/Serie

Algorithms and Computation, ISAAC 2014

Volym

8889

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

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

Conference name

25th International Symposium on Algorithms and Computation (ISAAC), 2014

Conference date

2014-12-15 - 2014-12-17

Conference place

Jeonju, Korea, Republic of

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 0302-9743
  • ISSN: 1611-3349
  • ISBN: 978-3-319-13074-3