Abstract
Under what conditions can a simple polygon be tiled by parallelograms? In this paper we give matching necessary and sufficient conditions on the polygon to be tilable and characterize the set of possible tilings. We also provide an efficient algorithm for constructing a tiling.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. Asano and T. Asano, Minimum Partition of Polygonal Regions into Trapezoids,IEEE Symp. on Foundations of Computer Science, 1983, pp. 233–241.
B. Chazelle, Triangulating a Simple Polygon in Linear Time,IEEE Symp. on Foundations of Computer Science, 1990, pp. 220–230.
B. Chazelle and J. Incerpi, Triangulation and Shape-Complexity,ACM Trans. Graphics, vol. 3, no. 2, 1984, pp. 135–152.
R. Cleve, Private communication.
D. P. Dobkin, D. L. Souvaine, and C. J. Van Wyk, Decomposition and Intersection of Simple Splinegons,Algorithmica, vol. 3, 1988, pp. 473–485.
H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.
L. R. Ford, Jr., and D. R. Fulkerson,Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
A. Fournier and D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems,ACM Trans. Graphics, vol. 3, no. 2, 1984, pp. 153–174.
M. J. Greenberg and J. R. Harper,Algebraic Topology; A First Course, Addison-Wesley, Reading, MA, 1981.
B. Grünbaum and G. C. Shephard,Tiling and Patterns, Freeman, New York, 1986.
R. Kenyon, Tiling a Polygon with Parallelograms, Manuscript.
T. Ohtsuki, Minimum Partition of Rectilinear Regions,IEEE Internat. Symp. on Circuits and Systems, 1982, pp. 1210–1213.
J. O'Rourke,Art Gallery Theorems and Algorithms, Oxford University Press, Oxford, 1987.
R. E. Tarjan and C. J. Van Wyk, AnO(n log logn)-Time Algorithm for Triangulating a Simple Polygon,SIAM J. Comput., vol. 17, no. 1, 1988, pp. 143–178.
W. P. Thurston, Conway's Tiling Groups,Amer. Math. Monthly, vol. 97, no. 8, 1990, pp. 757–773.
Author information
Authors and Affiliations
Additional information
This work was done while S. Kannan was with the University of California, Berkeley, and was supported by NSF Grant CCR 88-13632. The work of D. Soroker was done while he was with IBM Almaden Research Center.
Rights and permissions
About this article
Cite this article
Kannan, S., Soroker, D. Tiling polygons with parallelograms. Discrete Comput Geom 7, 175–188 (1992). https://doi.org/10.1007/BF02187834
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187834