Name: Optimal In-Place Compaction of Sliding Cubes
Keywords: Anàlisi numèrica, Computational Geometry (cs.CG), FOS: Computer and information sciences, Sliding cubes, Classificació AMS::68 Computer science::68U Computing methodologies and applications, Modular robots, Reconfiguration algorithm, Computing methodologies, 004, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Jan 2023Embargo end date: 01 Jan 2023Publisher:arXiv

Authors: Kostitsyna, Irina; Ophelders, Tim; Parada, Irene; Peters, Tom; Sonke, Willem; Speckmann, Bettina;

doi: 10.48550/arxiv.2312.15096

arXiv: 2312.15096

handle: 2117/424032

Optimal In-Place Compaction of Sliding Cubes

- Summary
- Subjects
- Metrics

Abstract

The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three.

Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260.

Peer Reviewed

Related Organizations

Universitat Politècnica de Catalunya
Spain
Leibniz Association
Germany
Universitat Polite`cnica de Catalunya
Spain
Schloss Dagstuhl – Leibniz Center for Informatics
Germany
Utrecht University
Netherlands

View all View all

Keywords

Anàlisi numèrica, Computational Geometry (cs.CG), FOS: Computer and information sciences, Sliding cubes, Classificació AMS::68 Computer science::68U Computing methodologies and applications, Modular robots, Reconfiguration algorithm, Computing methodologies, 004, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Computer Science - Robotics, Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi matemàtica, Informàtica, Computer Science - Computational Geometry, Àrees temàtiques de la UPC::Informàtica, Robotics (cs.RO), Numerical analysis, ddc: ddc:004

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Usage byUsageCounts

visibility	views	22
download	downloads	2

22
views
2
downloads
Powered by

Found an issue? Give us feedback

visibility

download

Average

Green

Related to Research communities

Netherlands Research Portal