International Journal of Computational Geometry & Applications

There exists a linear algorithm to decide whether a polyomino tessellates the plane by translation only. On the other hand, the problem of deciding whether a set of $11$ or more polyominoes can tile the plane by translation is undecidable. We narrow the gap between decidable and undecidable by showing that it remains undecidable for a set of $10$ polyominoes, which partially solves a conjecture posed by Ollinger.

We give some properties of semi-symmetric pseudo-Riemannian manifolds as an indecomposable irreducible Ricci pseudo-Riemannian manifold (i.e. the minimal polynomial of its Ricci operator is irreducible) is semi symmetric if and only if it is locally symmetric. We also show that any semi-symmetric pseudo-Riemannian manifold will be foliated. Moreover, if the metric is Lorentzian, the Ricci operator has only real eigenvalues and more precisely, on each leaf, it is diagonalizable with at most a single non zero eigenvalue or isotropic.

Various angle characteristics are used (e.g. in finite element methods or computer graphics) when evaluating the quality of computational meshes which may consist, in the three-dimensional case, of tetrahedra, prisms, hexahedra and pyramids. Thus, it is of interest to derive (preferably tight) bounds for dihedral angle sums, i.e. sums of angles between faces, of such mesh elements. For tetrahedra this task was solved by Gaddum in 1952. For pyramids, this was resolved by Korotov, Lund and Vatne in 2022. In this paper, we compute tight bounds for the remaining two cases, hexahedra and prisms.

In this paper, we consider enumeration of geodesics on a polyhedron, where a geodesic means locally-shortest path between two points. Particularly, we consider the following preprocessing problem: given a point $s$ on a polyhedral surface and a positive real number $r$, to build a data structure that enables, for any point $t$ on the surface, to enumerate all geodesics from $s$ to $t$ whose length is less than $r$. First, we present a naive algorithm by removing the trimming process from the MMP algorithm (1987). Next, we present an improved algorithm which is practically more efficient on a non-convex polyhedron, in terms of preprocessing time and memory consumption. Moreover, we introduce a single-pair geodesic graph to succinctly encode a result of geodesic query. Lastly, we compare these naive and improved algorithms by some computer experiments.

We study the Maximum Bipartite Subgraph ($MBS$) problem, which is defined as follows. Given a set $S$ of $n$ geometric objects in the plane, we want to compute a maximum-size subset $S^{\prime }\subseteq S$ such that the intersection graph of the objects in $S^{\prime }$ is bipartite. We first give an $O(n^2)$-time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the $MBS$ problem is $NP$-hard on geometric graphs for which the maximum independent set is $NP$-hard (hence, it is $NP$-hard even on unit squares and unit disks). On the other hand, we give a $PTAS$ for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks, and unit-height axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph ($MTFS$) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the $MBS$ except the intersection graph induced by the set $S^{\prime }$ needs to be triangle-free only (instead of being bipartite).