Tromino tilings of domino-deficient rectangles
Discrete Mathematics, 309(4):937-944 (2009).
We consider tromino tilings of m×n domino-deficient rectangles, where 3|(mn-2) and m,n&ge0, and characterize
all cases of domino removal that admit such tilings, thereby settling the open problem posed by Ash and Golomb in [J. Marshall Ash, S. Golomb,
Tiling Deficient Rectangles with Trominoes, Integre Technical Publishing Co., Mathematics Magazine (2003), 46-55]. We suggest a procedure
for tiling domino-deficient rectangles based on this characterization. We also consider general 2-deficiency in n×4 rectangles,
where n&ge8, and characterize all pairs of missing squares which do not permit a tromino tiling.
|
Triangulating the Real Projective Plane
written with Monique Teillaud, MACIS 2007.
We consider the problem of computing a triangulation of the real projective plane P2, given a finite point set
P = {p1,p2,...,pn} as input. We prove that a triangulation of P2 always exists if at least
six points in P are in general position, i.e., no three of them are collinear. We also design an algorithm
for triangulating P2 if this necessary condition holds. As far as we know, this is the first computational result
on the real projective plane.
|