Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCausal dynamics of discrete manifolds
100
0
0.0
(
0
)
Added by
Stefano Facchini
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We extend Cellular Automata to time-varying discrete geometries. In other words we formalize, and prove theorems about, the intuitive idea of a discrete manifold which evolves in time, subject to two natural constraints: the evolution does not propagate information too fast; and it acts everywhere the same. For this purpose we develop a correspondence between complexes and labeled graphs. In particular we reformulate the properties that characterize discrete manifolds amongst complexes, solely in terms of graphs. In dimensions $n<4$, over bounded-star graphs, it is decidable whether a Cellular Automaton maps discrete manifolds into discrete manifolds.
rate research
Read More
A Dubins path is a shortest path with bounded curvature. The seminal result in non-holonomic motion planning is that (in the absence of obstacles) a Dubins path consists either from a circular arc followed by a segment followed by another arc, or from three circular arcs [Dubins, 1957]. Dubins original proof uses advanced calculus; later, Dubins result was reproved using control theory techniques [Reeds and Shepp, 1990], [Sussmann and Tang, 1991], [Boissonnat, Cerezo, and Leblond, 1994]. We introduce and study a discrete analogue of curvature-constrained motion. We show that shortest bounded-curvature polygonal paths have the same structure as Dubins paths. The properties of Dubins paths follow from our results as a limiting case---this gives a new, discrete proof of Dubins result.
This work is thought as an operative guide to discrete exterior calculus (DEC), but at the same time with a rigorous exposition. We present a version of (DEC) on cubic cell, defining it for discrete manifolds. An example of how it works, it is done on the discrete torus, where usual Gauss and Stokes theorems are recovered.
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conways conjecture states that a thrackle has at most as many edges as vertices. In this paper, we investigate the edge-vertex ratio of maximal thrackles, that is, thrackles in which no edge between already existing vertices can be inserted such that the resulting drawing remains a thrackle. For maximal geometric and topological thrackles, we show that the edge-vertex ratio can be arbitrarily small. When forbidding isolated vertices, the edge-vertex ratio of maximal geometric thrackles can be arbitrarily close to the natural lower bound of 1/2. For maximal topological thrackles without isolated vertices, we present an infinite family with an edge-vertex ratio of 5/6.
We obtain improved upper bounds and new lower bounds on the chromatic number as a linear function of the clique number, for the intersection graphs (and their complements) of finite families of translates and homothets of a convex body in $RR^n$.
Let C be a simple, closed, directed curve on the surface of a convex polyhedron P. We identify several classes of curves C that live on a cone, in the sense that C and a neighborhood to one side may be isometrically embedded on the surface of a cone Lambda, with the apex a of Lambda enclosed inside (the image of) C; we also prove that each point of C is visible to a. In particular, we obtain that these curves have non-self-intersecting developments in the plane. Moreover, the curves we identify that live on cones to both sides support a new type of source unfolding of the entire surface of P to one non-overlapping piece, as reported in a companion paper.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
