An Escher-like tiling is a tiling consisting of one or a few artistic shapes of tile. This article proposes a method for generating Escher-like tilings consisting of two distinct shapes (dihedral Escher-like tilings) that are as similar as possible to the two goal shapes specified by the user. This study is an extension of a previous study that successfully generated Escher-like tilings consisting of a single tile shape for a single goal shape. Building upon the previous study, our method attempts to exhaustively search for which parts of the discretized tile contours are adjacent to each other to form a tiling. For each configuration, two tile shapes are optimized to be similar to the given two goal shapes. By evaluating the similarity based on as-rigid-as possible deformation energy, the optimized tile shapes preserve the local structures of the goal shapes, even if substantial deformations are necessary to form a tiling. However, in the dihedral case, this approach is seemingly unrealistic because it suffers from the complexity of the energy function and the combinatorial explosion of the possible configurations. We developed a method to address these issues and show that the proposed algorithms can generate satisfactory dihedral Escher-like tilings in a realistic computation time, even for somewhat complex goal shapes.

Escher tiling is well known as a tiling that consists of one or a few recognizable figures, such as animals. The Escherization problem involves finding the most similar shape to a given goal figure that can tile the plane. However, it is easy to imagine that there is no similar tile shape for complex goal shapes. This article devises a method for finding a satisfactory tile shape in such a situation. To obtain a satisfactory tile shape, the tile shape is generated by deforming the goal shape to a considerable extent while retaining the characteristics of the original shape. To achieve this, both goal and tile shapes are represented as triangular meshes to consider not only the contours but also the internal similarity of the shapes. To measure the naturalness of the deformation, energy functions based on traditional as-rigid-as-possible shape modeling are incorporated into a recently developed framework of the exhaustive search of the templates for the Escherization problem. The developed algorithms find satisfactory tile shapes with natural deformations for fairly complex goal shapes.

In this paper, we optimize train stopping patterns during morning rush hour in Japan. Since trains are extremely crowded, we need to determine stopping patterns based not only on travel time but also on congestion rates of trains. We exploit a Wardrop equilibrium model to compute passenger flows subject to congestion phenomena and present an efficient local search algorithm to optimize stopping patterns which iteratively computes a Wardrop equilibrium. We apply our algorithm to railway lines in Tokyo including Keio Line with six types of trains and succeed in relaxing congestion with a small effect on travel time.

Abstract This article describes a node capacitated in‐tree packing problem. The input consists of a directed graph, a root node, a node capacity function, and edge consumption functions. The problem is to find the maximum number of rooted in‐trees, such that the total consumption of in‐trees at each node does not exceed the capacity of the node. The problem is one of the network lifetime problems that are among the most important issues in the context of sensor networks. We establish the computational complexity of the problem under various restrictions on consumption functions and graphs. For example, we consider general graphs, acyclic graphs, and complete graphs embedded in the d ‐dimensional space \input amssym ${\Bbb{R}}^d$ having edge consumption functions depending only on distances between end nodes. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

In hop-by-hop networks, provision of multipath routes for all nodes can improve fault tolerance and performance. In this paper we study the multipath route calculation by constructing a directed acyclic graph (DAG) which includes all edges in the network. We define new DAG construction problems with the objectives of 1) maximizing the minimum connectivity, 2) maximizing the minimum max-flow, and 3) maximizing the minimum max-flow as an extension of shortest path routing. A family of new algorithms called Maximum Alternative Routing Algorithms (MARAs) is described, proven formally to solve the problems optimally, and contrasted with existing multipath algorithms. MARAs are evaluated for the number of paths, the length of paths, the computational complexity, and the computation time, using simulations based on several real Internet Autonomous System (AS) network topologies. We show that MARAs run in sub-second times on moderate-speed processors and achieve a significant increase in the number of paths compared to existing multipath routing algorithms. These results should help further the process of deploying multipath routing in real-world networks.