3D rectangulations and geometric matrix multiplication

DOI10.1007/S00453-016-0247-3zbMath1386.68195OpenAlexW2614723287MaRDI QIDQ1702124

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

Publication date: 28 February 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0247-3

zbMATH Keywords

time complexitymatrix multiplicationdecomposition problemorthogonal polyhedronminimum rectangulation

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (1)

Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rectangular partition is polynomial in two dimensions but NP-complete in three
• A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs
• Finding a manhattan path and related problems
• Powers of tensors and fast matrix multiplication
• Algorithms and Data Structures

This page was built for publication: 3D rectangulations and geometric matrix multiplication