Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath
<p><strong>Thai Journal of Mathematics</strong><br />Thai Journal of Mathematics (TJM) is a peer-reviewed, open access international journal publishing original research works of high standard in all areas of pure and applied mathematics.</p> <p><br /><strong>Publication Frequency</strong><br />From 2020 onwards, TJM publishes one volume per year which consists of four regular issues (March, June, September, and December). All manuscripts are refereed under the same standards as those used by the finest-quality printed mathematical journals. Accepted papers will be published online in their final forms using the TJM template and will be published in four issues annually.</p>en-USthaijmath@cmu.ac.th (Prof.Dr. Suthep Suantai)thaijmath@cmu.ac.th (Support Team)Sun, 31 Dec 2023 00:00:00 +0000OJS 3.3.0.14http://blogs.law.harvard.edu/tech/rss60Celeste is PSPACE-hard
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1538
<p>We investigate the complexity of the platform video game Celeste. We prove that navigating Celeste is PSPACE-hard in five different ways, corresponding to different subsets of the game mechanics. In particular, we prove the game PSPACE-hard even without player input.</p>Lily Chung, Erik D. Demaine
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1538Sun, 31 Dec 2023 00:00:00 +0000The Legend of Zelda: The Complexity of Mechanics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1539
<p>We analyze some of the many game mechanics available to Link in the classic Legend of Zelda series of video games. In each case, we prove that the generalized game with that mechanic is polynomial, NP-complete, NP-hard and in PSPACE, or PSPACE-complete. In the process we give an overview of many of the hardness proof techniques developed for video games over the past decade: the motion-planning-through-gadgets framework, the planar doors framework, the doors-and-buttons framework, the "Nintendo" platform game / SAT framework, and the collectible tokens and toll roads / Hamiltonicity framework.</p>Jeffrey Bosboom, Josh Brunner, Michael Coulombe, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch, Elle Najt
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1539Sun, 31 Dec 2023 00:00:00 +0000Previous Player's Positions of Impartial Three-Dimensional Chocolate-Bar Games
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1540
<p>In this study, we investigate three-dimensional chocolate bar games, which are variants of the game of Chomp. A three-dimensional chocolate bar is a three-dimensional array of cubes in which a bitter cubic box is present in some part of the bar. Two players take turns and cut the bar horizontally or vertically along the grooves. The player who manages to leave the opponent with a single bitter block is the winner. We consider the $\mathcal{P}$-positions of this game, where the $\mathcal{P}$-positions are positions of the game from which the previous player (the player who will play after the next player) can force a win, as long as they play correctly at every stage. We present sufficient conditions for the case when the position $(p,q,r)$ is a $\mathcal{P}$-position if and only if $(p-1) \oplus (q-1) \oplus (r-1)$, where $p, q$, and $r$ are the length, height, and width of the chocolate bar, respectively.</p>Ryohei Miyadera, Shunsuke Nakamura, Hikaru Manabe
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1540Sun, 31 Dec 2023 00:00:00 +0000Maximum Nim and Chocolate Bar Games
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1541
<p>The authors studied maximum Nim wherein each player can remove at most $f(m)$ stones from a pile of $m$ stones, where $f(m)= \left\lceil \frac{m}{d} \right\rceil $ or $f(m)= \left\lfloor \frac{m+1}{d}\right\rfloor $ with a positive number $d$ that is larger than 1, and present function $h_{d}$ such that $\mathcal{G}(h_{d}(x)) = \mathcal{G}(x)$, where $\mathcal{G}(x)$ is the Grundy number of the pile of $x$ stones. The authors apply function $h_{d}$ to the study of chocolate bar games, wherein two players take turns and cut a chocolate bar in a straight line and eat the pieces. These games can be considered the sum of two maximum Nim with a restriction on the size of the chocolate bar that can be eaten by the players. Therefore, using $h_{d}$, the authors devise formulas to calculate the winning position of the previous player for a rectangular chocolate bar game with a restriction on the size of the chocolate bar piece to be eaten. In addition, the authors present conjectures about rectangular chocolate bar games with some missing parts.</p>Ryohei Miyadera, Sohta Kannan, Hikaru Manabe
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1541Sun, 31 Dec 2023 00:00:00 +0000Feedback Game on Eulerian Graphs
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1542
<p>In this paper, we introduce a two-player impartial game on graphs, called feedback game, which is a variant of generalized geography. Feedback game can be regarded as undirected edge geography with an additional rule that the first player who goes back to the starting vertex wins the game. We consider feedback game on an Eulerian graph since the game ends only by going back to the starting vertex. We first show that it is PSPACE-complete in general to determine the winner of the feedback game on Eulerian graphs even if its maximum degree is at most~4. In the latter half of the paper, we discuss the feedback game on two subclasses of Eulerian graphs, i.e., triangular grid graphs and toroidal grid graphs.</p>Naoki Matsumoto, Atsuki Nagao
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1542Sun, 31 Dec 2023 00:00:00 +0000Playing Impartial Games on a Simplicial Complex as an Extension of the Emperor Sum Theory
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1543
<p>In this paper, we considered impartial games on a simplicial complex. Each vertex of a given simplicial complex acts as a position of an impartial game. Each player in turn chooses a face of the simplicial complex and, for each position on each vertex of that face, the player can make an arbitrary number of moves. Moreover, the player can make only a single move for each position on each vertex, not on that face. We show how the $\mathcal{P}$-positions of this game can be characterized using the $\mathcal{P}$-position length. This result can be considered an extension of the emperor sum theory. While the emperor sum only allowed multiple moves for a single component, this study examines the case where multiple moves can be made for multiple components, and clarifies areas that the emperor sum theory did not cover.</p>Koki Suetsugu
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1543Sun, 31 Dec 2023 00:00:00 +0000Biased Domination Games
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1544
<p>We introduce an extended version of a domination game on a graph, called a biased domination game, in which Dominator or Staller plays more than one move in each turn. We show some relations of biased game domination numbers for different biases.</p>Tharit Sereekiatdilok, Panupong Vichitkunakorn
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1544Sun, 31 Dec 2023 00:00:00 +0000On the Complexity of Motion Planning Problem of a Forklift
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1545
<p>The robot motion planning problem is one of the most studied problems in computational geometry in continuous settings. We study the Forklift Motion Planning Problem, which is defined based on a puzzle called Zaikoban, in a discrete setting of 3-dimensional space. We demonstrate that the configuration space method can be applied to the discrete case. In particular, we show that the forklift motion planning problem is solvable in polynomial time for the one-box case, and show that the general forklift motion planning problem with multiple boxes is PSPACE-complete by reduction to the nondeterministic constraint logic (NCL) problem.</p>Chao Yang
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1545Sun, 31 Dec 2023 00:00:00 +0000Graph of $uv$-Paths in Connected Graphs
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1546
<p>For a connected graph $G$ and vertices $u,v$ of $G$ we define an abstract graph $\mathcal{P}(G_{uv})$ whose vertices are the paths joining $u$ and $v$ in $G$, where paths $S$ and $T$ are adjacent if $T$ is obtained from $S$ by replacing a subpath $S_{xy}$ of $S$ with an internally disjoint subpath $T_{xy}$ of $T$. Let $\mathcal{C}$ be a set of cycles of $G$; the \emph{$uv$-path graph of $G$ defined by $\mathcal{C}$} is the spanning subgraph $\mathcal{P}_\mathcal{C}(G_{uv})$ of $\mathcal{P}(G_{uv})$ in which two paths $S$ and $T$ are adjacent if and only if the unique cycle $\sigma$ contained in $S\cup T$ lies in $\mathcal{C}$. We prove that $\mathcal{P}(G_{uv})$ is always connected and give a necessary condition and a sufficient condition for a graph $\mathcal{P}_\mathcal{C}(G_{uv})$ to be connected.</p>Eduardo Rivera-Campo
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1546Sun, 31 Dec 2023 00:00:00 +0000Linear-Time Rectilinear Drawings of Subdivisions of Triconnected Cubic Planar Graphs with Orthogonally Convex Faces
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1547
<p>A graph is called planar if it admits a planar drawing on the plane, i.e., no two edges create a crossing except possibly at their common endpoint. In a rectilinear drawing $\Gamma$ of a planar graph, each vertex is drawn as a point and each edge is drawn as either horizontal or vertical line segment. A face in $\Gamma$ is called orthogonally convex if every horizontal or vertical line segment connecting two points within the face does not intersect any other face. We examine the decision problem that takes a planar graph as an input and seeks for a rectilinear drawing where the faces are drawn as orthogonally convex polygons. A linear-time algorithm for this problem is known for biconnected planar graphs, but the algorithm relies on complex data structures and linear-time planarity testing, which are challenging to implement. In this paper, we give a necessary and sufficient condition for a subdivision of a triconnected cubic planar graph to admit such a drawing, and design a linear-time algorithm to check the condition and compute a desired drawing, if it exists. As a byproduct of our results we show that if a subdivision of a triconnected cubic planar graph $G$ admits a rectilinear drawing, then it must also admit a rectilinear drawing with orthogonally convex faces.</p>Md. Manzurul Hasan, Debajyoti Mondal, Md. Saidur Rahman
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1547Sun, 31 Dec 2023 00:00:00 +0000On the Rainbow Mean Indexes of Caterpillars
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1548
<p>Let $G$ be a simple connected graph and $c$ an edge coloring with colors that are positive integers. Given a vertex $v$ of $G,$ we define its chromatic mean, denoted by cm$\left( v\right) $, as the average of the colors of the incident edges. If cm$\left( v\right) $ is an integer for each $v\in V\left( G\right) $ and distinct vertices have distinct chromatic means, then $c$ is called a rainbow mean coloring. The maximum chromatic mean of a vertex in the coloring $c$ is called the rainbow mean index of $c$ and is denoted by rm$\left( c\right) $. On the other hand, the rainbow mean index of $G$, denoted by $\operatorname{rm}(G)$, is the minimum value of rm$\left( c\right) $ among all rainbow mean colorings $c$ of $G$. In this paper, we determine the rainbow mean indexes of families of caterpillars, including brooms, and double brooms.</p>Agnes D. Garciano, Reginaldo M. Marcelo, Mari-Jo P. Ruiz, Mark Anthony C. Tolentino
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1548Sun, 31 Dec 2023 00:00:00 +0000On the Set Chromatic Number of the Middle Graph of Extended Stars and Related Tree Families
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549
<p>Suppose $G$ is a simple, undirected, finite, nontrivial, and connected graph and that $c: V(G) \to \mathbb{N}$ is a vertex coloring, not necessarily proper, of $G$. As introduced by Chartrand et al., $c$ is called a set coloring of $G$ if $NC(u) \neq NC(v)$ for every pair of adjacent vertices $u$ and $v$; here, $NC(x)$ denotes the set of colors of all the neighbors of the vertex $x$. Moreover, the set chromatic number of $G$, denoted by $\chi_s(G)$, is the minimum number of colors that can be used to construct a set coloring of $G$. On the other hand, the middle graph $M(G)$ of a graph $G$ is defined as the graph whose vertex set is $V(G) \cup E(G)$ and in which two vertices $u$ and $v$ are adjacent if and only if $u$ and $v$ are adjacent edges in $G$; or $u \in V(G)$, $v \in E(G)$, and $u$ is incident to $v$ in $G$. In this paper, we study set colorings in relation to the middle graph of some tree families. We establish lower bounds for the set chromatic number of these graphs and we algorithmically construct set colorings for them. For most cases, we find that the set chromatic number for these graphs is given by min-max formulas.</p>Mark Anthony C. Tolentino, Gerone Russel J. Eugenio
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1549Sun, 31 Dec 2023 00:00:00 +0000Non-crossing Monotone Paths and Cycles through Specified Points of Labeled Point Sets
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1550
<p>Let $P$ be a set of $n$ points in convex position in the plane, each of which is assigned a different number, called a label. A path whose vertices are points of $P$ is called monotone if the labels of its vertices increase while traversing it starting from one of its end vertices. We show that for any element $q \in P$, there is a non-crossing monotone path containing $q$ connecting at least $\bigl\lceil \sqrt{2(n-1)}\, \bigr\rceil$ elements. This bound is almost tight. A simple polygon with vertices in $P$ is called monotone if it consists of a monotone path and the line segment connecting its endpoints. The polygon is monotonically increasing (respectively decreasing) if when we traverse it in the clockwise direction starting at one of its vertices, the labels of its vertices increase (respectively decrease). We call such a simple polygon an increasing (respectively a decreasing) cycle. We also prove that any set $P$ of $(l-1)(m-1)+2$ labeled points in general position in the plane, and for any point $q \in P$ on the boundary of the convex hull of $P$, there exists an increasing cycle containing $q$ with at least $l+1$ elements, or a decreasing cycle containing $q$ with at least $m+1$ elements.</p>Toshinori Sakai, Jorge Urrutia
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1550Sun, 31 Dec 2023 00:00:00 +0000Soft Semigraphs and Different Types of Degrees, Graphs and Matrices Associated with Them
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1551
<p>This is an introductory paper on soft semigraphs. Semigraph is a generalization of graph introduced by E. Sampathkumar which is different from hypergraph. In 1999, D. Molodtsov initiated the novel concept of soft set theory. This is an approach for modelling vagueness and uncertainty. It is a classification of elements of the universe with respect to some given set of parameters. The concept of soft graph introduced by Rajesh K. Thumbakara and Bobin George is used to provide a parameterized point of view for graphs. The theory of soft graphs is a fast developing area in graph theory due to its capability to deal with the parameterization tool. In this paper, we introduce soft semigraph by applying the concept of soft set in semigraph. Also, we introduce different types of degrees, graphs and matrices associated with a soft semigraph and investigate some of their properties.</p>Bobin George, Rajesh K. Thumbakara, Jinta Jose
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1551Sun, 31 Dec 2023 00:00:00 +0000On the Connectivity of Non-Commuting Graph of Finite Rings
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1554
<p>The non-commuting graph of a non-commutative ring $R$, denoted by $\Gamma_{R}$, is a simple graph with vertex set of elements in $R$ except for its center. Two distinct vertices $x$ and $y$ are adjacent if $xy \neq yx$. In this paper, we study the vertex-connectivity and edge-connectivity of a non-commuting graph associated with a finite non-commutative ring $R$ and prove their lower bounds. We show that the edge-connectivity of $\Gamma_{R}$ is equal to its minimum degree. The vertex-connectivity and edge-connectivity of $\Gamma_{R}$ are determined when $R$ is a non-commutative ring of order $p^{n}$ where $p$ is a prime number, and $n \in \left\{2,3,4,5\right\}$.</p>Borworn Khuhirun, Khajee Jantarakhajorn, Wanida Maneerut
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1554Sun, 31 Dec 2023 00:00:00 +0000Uniformly Generating Derangements with Fixed Number of Cycles in Polynomial Time
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1555
<p>We study the uniform sampling of permutations without fixed points, i.e., derangements, that can be decomposed into $m$ disjoint cycles. Since the number of cycles in a random derangement tends towards the standard distribution, rejection sampling may take exponential time when $m$ largely deviates from the mean of $\Theta(\log n)$. We propose an algorithm for generating a uniformly random derangement of $n$ items with $m$ cycles in $O(n^{2.5}\log n)$ time complexity using dynamic programming with an assumption that all arithmetic operations can be done in time $O(1)$. Taking into account the arithmetic operations on large integers, the running time becomes $O(n^{3.5}\log^3 n)$. Our algorithm uses permutation types to structure our uniform generation of derangements.</p>Nattawut Phetmak, Jittat Fakcharoenphol
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1555Sun, 31 Dec 2023 00:00:00 +0000On the Number of $k$-Proper Connected Edge and Vertex Colorings of Graphs
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1556
<p>An edge (resp. vertex) coloring of a graph using a palette of $w$ colors is called a $k$-proper connected (resp. vertex-$k$-proper connected) $w$-coloring if and only if there exist at least $k$ vertex disjoint paths between all pairs of vertices having no two adjacent edges (resp. vertices) of the same color. In this work, we characterize the hardness of counting and approximately counting $k$-proper connected and vertex-$k$-proper connected colorings of graphs under color palette cardinality, vertex degree, bipartiteness, and planarity restrictions. In particular, we show that the problem of counting $k$-proper connected $(w=2)$-colorings and vertex-$k$-proper connected $(w=2)$-colorings of bipartite graphs is $\#P$-complete $\forall k \in \mathbb{N}_{>0}$, and that these results hold for subcubic bipartite planar graphs in the $k=1$ case. With regard to approximate counting, among other findings we show that a Fully Polynomial-time Randomized Approximation Scheme (FPRAS) for counting $k$-proper connected $(w=2)$-colorings and vertex-$k$-proper connected $(w=2)$-colorings of bipartite graphs, for any $k \in \mathbb{N}_{>0}$, implies an FPRAS for counting strong orientations and spanning connected subgraphs, respectively, of arbitrary undirected simple graphs.</p>Robert D. Barish
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1556Sun, 31 Dec 2023 00:00:00 +0000Direction-Critical Configurations in Noncentral General Position
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1557
<p>In 1982, Ungar proved that the connecting lines of a set of $n$ noncollinear points in the plane determine at least $2\lfloor n/2 \rfloor$ directions (slopes). Sets achieving this minimum for $n$ odd (even) are called direction-(near)-critical and their full classification is still open. To date, there are four known infinite families and over 100 sporadic critical configurations. Jamison conjectured that any direction-critical configuration with at least 50 points belongs to those four infinite families. Interestingly, except for a handful of sporadic configurations, all these configurations are centrally symmetric. We prove Jamison's conjecture, and extend it to the near-critical case, for centrally symmetric configurations in noncentral general position, where only the connecting lines through the center of symmetry may pass through more than two points. As in Ungar's proof, our results are proved in the more general setting of allowable sequences. We show that, up to equivalence, the central signature of a set uniquely determines a centrally symmetric direction-(near)-critical allowable sequence in noncentral general position, and classify such allowable sequences that are geometrically realizable.</p>Silvia Fernandez-Merchant, Rimma Hamalainen
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1557Sun, 31 Dec 2023 00:00:00 +0000Multifold Tiles of Polyominoes and Convex Lattice Polygons
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1559
<p>A planar shape $S$ is a $k$-fold tile if there is an indexed family $\mathcal{T}$ of planar shapes congruent to $S$ that is a $k$-fold tiling: any point in $\mathbb{R}^2$ that is not on the boundary of any shape in $\mathcal{T}$ is covered by exactly $k$ shapes in $\mathcal{T}$. Since a 1-fold tile is clearly a $k$-fold tile for any positive integer $k$, the subjects of our research are \emph{nontrivial $k$-fold tiles}, that is, plane shapes with property "not a 1-fold tile, but a $k(\geq 2)$-fold tile." In this paper, we prove some interesting properties about nontrivial $k$-fold tiles. First, we show that, for any integer $k \geq 2$, there exists a polyomino with property "not an $h$-fold tile for any positive integer $h<k$, but a $k$-fold tile." We also find, for any integer $k \geq 2$, polyominoes with the minimum number of cells among ones that are nontrivial $k$-fold tiles. Next, we prove that, for any integer $k=5$ or $k \geq 7$, there exists a convex unit-lattice polygon that is a nontrivial $k$-fold tile whose area is $k$, and for $k=2$ and $k=3$, no such convex unit-lattice polygon exists.</p>Kota Chida, Erik D. Demaine, Martin L. Demaine, David Eppstein, Adam Hesterberg, Takashi Horiyama, John Iacono, Hiro Ito, Stefan Langerman, Ryuhei Uehara, Yushi Uno
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1559Sun, 31 Dec 2023 00:00:00 +0000Parallel Curve Detection Method based on Hough Transform
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1560
<p>Hough transform is a widely used approach for recognizing straight lines and circles. Recently, an extension was published, allowing us to detect a larger class of algebraic curves. The image with parallel curves is the subject of this study. An incorrect curve may be detected using the standard approach. We modify the accumulator function and introduce the concept of parallel curves into the detection method to tackle this problem. Synthetic and real-world images are used to demonstrate the effectiveness of this method.</p>Nattapol Chanpaisit, Pat Vatiwutipong
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1560Sun, 31 Dec 2023 00:00:00 +0000Wang Tiles: Connectivity when Tiling a Plane
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1561
<p>Inspired by the Nintendo game Zelda, the problem of tessellating the plane by translated copies from a set of Wang tiles is generalized to the connected tiling problem. We solve the connected tiling problem for the case that there is only one door color and one wall color in this paper.</p>Chao Yang
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1561Sun, 31 Dec 2023 00:00:00 +0000Unfolding Orthotubes with a Dual Hamiltonian Path
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1562
<p>An orthotube consists of orthogonal boxes (e.g., unit cubes) glued face-to-face to form a path. In 1998, Biedl et al. showed that every orthotube has a grid unfolding: a cutting along edges of the boxes so that the surface unfolds into a connected planar shape without overlap. We give a new algorithmic grid unfolding of orthotubes with the additional property that the rectangular faces are attached in a single path -- a Hamiltonian path on the rectangular faces of the orthotube surface.</p>Erik D. Demaine, Kritkorn Karntikoon
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1562Sun, 31 Dec 2023 00:00:00 +0000Complexity of Simple Folding of Mixed Orthogonal Crease Patterns
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1563
<p>Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of the simple foldability problem -- deciding which crease patterns can be folded flat by a sequence of (some model of) simple folds. We give new efficient algorithms for mixed crease patterns, where some creases are assigned mountain/valley while others are unassigned, for all 1D cases and for 2D rectangular paper with orthogonal one-layer simple folds. By contrast, we show strong NP-completeness for mixed orthogonal crease patterns on 2D rectangular paper with some-layers simple folds, complementing a previous result for all-layers simple folds. We also prove strong NP-completeness for finite simple folds (no matter the number of layers) of unassigned orthogonal crease patterns on arbitrary paper, complementing a previous result for assigned crease patterns, and contrasting with a previous positive result for infinite all-layers simple folds. In total, we obtain a characterization of polynomial vs.\ NP-hard for all cases -- finite/infinite one/some/all-layers simple folds of assigned/unassigned/mixed orthogonal crease patterns on 1D/rectangular/arbitrary paper -- except the unsolved case of infinite all-layers simple folds of assigned orthogonal crease patterns on arbitrary paper.</p>Hugo Akitaya, Josh Brunner, Erik D. Demaine, Dylan Hendrickson, Victor Luo, Andy Tockman
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1563Sun, 31 Dec 2023 00:00:00 +0000Orthogonal Fold & Cut
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1564
<p>We characterize the cut patterns that can be produced by "orthogonal fold & cut": folding an axis-aligned rectangular sheet of paper along horizontal and vertical creases, and then making a single straight cut (at any angle). Along the way, we solve a handful of related problems: orthogonal fold & punch, 1D fold & cut, signed 1D fold & cut, and 1D interval fold & cut.</p>Joshua Ani, Josh Brunner, Erik D. Demaine, Martin L. Demaine, Dylan Hendrickson, Victor Luo, Rachana Madhukara
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1564Sun, 31 Dec 2023 00:00:00 +0000Clarifying the Difference between Origami Fold Models by a Matrix Representation
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1565
<p>In this paper, we investigate the accessible flat-folded states of three common fold models under the context of two origami problems. The three fold models are the simple fold model, the simple fold-unfold model, and the general fold model. The two problems are the valid total order problem (VTP) and the valid boundary order problem (VBP). They both belong to the field of computational origami and are considered as two variants of the map folding problem. As a result, in both VTP and VBP, the proper inclusion relationship between the sets of the accessible valid orders of the simple fold model and the simple fold-unfold model, and the proper inclusion relationship between the sets of the accessible valid orders of the simple fold-unfold model and the general fold model are clarified. We first introduce a four-dimensional logical matrix representation to prove these proper inclusions mathematically. Then, we further explain the proper inclusion relationship by actual map folding examples. This work extends our previous result: using the logical matrix representation to indicate arbitrary map foldings, where we have discussed the logical matrix representation from the viewpoint of category theory. This time, instead of theoretical analysis, we realign the logical matrix to a four-dimensional form and use it to investigate VTP and VBP.</p>Yiyang Jia, Jun Mitani, Ryuhei Uehara
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1565Sun, 31 Dec 2023 00:00:00 +0000Mobius Flowers
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1566
<p>If you bisect conjoined two Mobius bands along each centerline, some of them end in interlocking hearts, and the others end in two separate hearts. What makes the difference between the happy outcome and the unhappy one? In this paper, we unravel this "Mobius Love-Fate problem" by using the concept of knot theory, as well as generalizing this theorem in various ways.</p>Jin Akiyama, Kiyoko Matsunaga, Sachiko Nakajima
Copyright (c) 2023 Thai Journal of Mathematics
https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1566Sun, 31 Dec 2023 00:00:00 +0000