We explore whether combinatorial game theory (CGT) is suitable for analyzing endgame positions in Xiangqi (Chinese Chess). We discover some of the game values that can also be found in the analysis of International Chess, but we also experience the limitations of CGT when applied to a loopy and non-separable game like Xiangqi.
In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size SUMw freq(w) size(c(w)). The problem has a well-known polynomial-time algorithm due to Huffman.
Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length SUMw freq(w) cost(c(w)), where cost(s) is the sum of the (possibly non-uniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.
The Welch lower bound on the total-squared-correlation (TSC) of binary signature sets is loose for binary signature sets whose length L is not a multiple of 4. Recently Karystinos and Pados developed new bounds that are better than the Welch bound in those cases, and showed how to achieve the bounds with modified Hadamard matrices except in a couple of cases. In this paper, we study the open cases.
A hierarchical decomposition of a simple polygon is introduced. The hierarchy has depth O(logn), linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon can be answered in O(log2 n) query time and O(nlogn) space. If the radius of the circle is fixed, the query time can be improved to O(logn) and the space to O(n).
Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves. We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone.
Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides view-dependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of n vertices and genus g, we prove that there is a constant c > 0 such that if n > c·g, then a greedy strategy can identify Theta(n) topology-preserving edge contractions that do not interfere with each other. Further, they affect only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of O(n + g2) size and O(logn + g) depth. The genus g is very small when compared with n for large models in practice. The identification of edges can be enhanced by selecting edges based on the error of their contractions as measured by some known heuristics. This will keep the geometric approximation small in practice. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a provably good hierarchy. When no contractible edge exists, the triangulation is irreducible. The best known upper bound on the number of vertices of an irreducible triangulation of an orientable 2-manifold is 342g-72 by Nakamoto and Ota. Using our proof techniques we obtain a new bound of 240g.
Extended context-free grammars are context-free grammars in which the right-hand sides of productions are allowed to be any regular language rather than being restricted being only finite languages. We develop a novel approach to top-down predictive parser construction for extended context-free grammars that is based on the rewriting of partial syntax trees.
This work is motivated by our development of ECFG, a Java toolkit for the manipulation of extended context-free grammars, and by our continuing investigation of XML.
Kirchhoff's Matrix Tree Theorem permits the calculation of the number of spanning trees in any given graph G through the evaluation of the determinant of an associated matrix. In the case of some special graphs Boesch and Prodinger have shown how to use properties of Chebyshev polynomials to evaluate the associated determinants and derive closed formulas for the number of spanning trees of graphs.
In this paper we extend this idea and describe how to use Chebyshev polynomials to evaluate the number of spanning trees in G when G belongs to one of three different classes of graphs: (i) when G is a circulant graph with fixed jumps (substantially simplifying earlier proofs), (ii) when G is a circulant graph with some non-fixed jumps and when (ii) G= Kn ±C where Kn is the complete graph on n vertices and C is a circulant graph.