Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParticle-Based Assembly Using Precise Global Control
44
0
0.0
(
0
)
Added by
Christian Rieck
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In micro- and nano-scale systems, particles can be moved by using an external force like gravity or a magnetic field. In the presence of adhesive particles that can attach to each other, the challenge is to decide whether a shape is constructible. Previous work provides a class of shapes for which constructibility can be decided efficiently, when particles move maximally into the same direction on actuation. In this paper, we consider a stronger model. On actuation, each particle moves one unit step into the given direction. We prove that deciding constructibility is NP-hard for three-dimensional shapes, and that a maximum constructible shape can be approximated. The same approximation algorithm applies for 2D. We further present linear-time algorithms to decide whether a tree-shape in 2D or 3D is constructible. If scaling is allowed, we show that the $c$-scaled copy of every non-degenerate polyomino is constructible, for every $c geq 2$.
rate research
Read More
We prove that by successively combining subassemblies, we can achieve sublinear construction times for staged assembly of micro-scale objects from a large number of tiny particles, for vast classes of shapes; this is a significant advance in the context of programmable matter and self-assembly for building high-yield micro-factories.The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle; particles bond when forced together with a compatible particle. Previous work considered sequential composition of objects, resulting in construction time that is linear in the number N of particles, which is inefficient for large N. Our progress implies critical speedup for constructible shapes; for convex polyominoes, even a constant construction time is possible. We also show that our construction process can be used for pipelining, resulting in an amortized constant production time.
The problem of {em efficiently} finding the best match for a query in a given set with respect to the Euclidean distance or the cosine similarity has been extensively studied in literature. However, a closely related problem of efficiently finding the best match with respect to the inner product has never been explored in the general setting to the best of our knowledge. In this paper we consider this general problem and contrast it with the existing best-match algorithms. First, we propose a general branch-and-bound algorithm using a tree data structure. Subsequently, we present a dual-tree algorithm for the case where there are multiple queries. Finally we present a new data structure for increasing the efficiency of the dual-tree algorithm. These branch-and-bound algorithms involve novel bounds suited for the purpose of best-matching with inner products. We evaluate our proposed algorithms on a variety of data sets from various applications, and exhibit up to five orders of magnitude improvement in query time over the naive search technique.
Human subject studies that map-like visualizations are as good or better than standard node-link representations of graphs, in terms of task performance, memorization and recall of the underlying data, and engagement [SSKB14, SSKB15]. With this in mind, we propose the Zoomable Multi-Level Tree (ZMLT) algorithm for multi-level tree-based, map-like visualization of large graphs. We propose seven desirable properties that such visualization should maintain and an algorithm that accomplishes them. (1) The abstract trees represent the underlying graph appropriately at different level of details; (2) The embedded trees represent the underlying graph appropriately at different levels of details; (3) At every level of detail we show real vertices and real paths from the underlying graph; (4) If any node or edge appears in a given level, then they also appear in all deeper levels; (5) All nodes at the current level and higher levels are labeled and there are no label overlaps; (6) There are no edge crossings on any level; (7) The drawing area is proportional to the total area of the labels. This algorithm is implemented and we have a functional prototype for the interactive interface in a web browser.
We propose a new quantum numerical scheme to control the dynamics of a quantum walker in a two dimensional space-time grid. More specifically, we show how, introducing a quantum memory for each of the spatial grid, this result can be achieved simply by acting on the initial state of the whole system, and therefore can be exactly controlled once for all. As example we prove analytically how to encode in the initial state any arbitrary walkers mean trajectory and variance. This brings significantly closer the possibility of implementing dynamically interesting physics models on medium term quantum devices, and introduces a new direction in simulating aspects of quantum field theories (QFTs), notably on curved manifold.
Some methods based on simple regularizing geometric element transformations have heuristically been shown to give runtime efficient and quality effective smoothing algorithms for meshes. We describe the mathematical framework and a systematic approach to global optimization-bas
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
