Partitioning parameterized 45-degree polygons with constraint programming

Tseng, I-L. and Postula, A.J. (2008) Partitioning parameterized 45-degree polygons with constraint programming. Transactions on Design Automation of Electronic Systems, 13 3: 52:1-52:29. doi:10.1145/1367045.1367061

Author Tseng, I-L.
Postula, A.J.
Title Partitioning parameterized 45-degree polygons with constraint programming
Journal name Transactions on Design Automation of Electronic Systems   Check publisher's open access policy
ISSN 1084-4309
Publication date 2008-07-01
Sub-type Article (original research)
DOI 10.1145/1367045.1367061
Open Access Status
Volume 13
Issue 3
Start page 52:1
End page 52:29
Total pages 29
Editor Irwin, M.J.
Place of publication USA
Publisher ACM
Language eng
Subject C1
861603 Integrated Circuits and Devices
080299 Computation Theory and Mathematics not elsewhere classified
Abstract An algorithm for partitioning parameterized 45-degree polygons into parameterized trapezoids is proposed in this article. The algorithm is based on the plane-sweep technique and can handle polygons with complicated constraints. The input to the algorithm consists of the contour of a parameterized polygon to be partitioned and a set of constraints for parameters of the contour. The algorithm uses horizontal cuts only and generates a number of nonoverlapping trapezoids whose union is the original parameterized polygon. Processing of constraints and coordinates that contain first-order multiple-variable polynomials has been made possible by incorporating the JaCoP constraint programming library. The proposed algorithm has been implemented in Java programming language and can be used as the basis to build the trapezoidal corner stitching data structure for parameterized VLSI layout masks.
Q-Index Code C1
Q-Index Status Confirmed Code

Document type: Journal Article
Sub-type: Article (original research)
Collections: 2009 Higher Education Research Data Collection
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 8 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 17 Apr 2009, 04:16:57 EST by Ms Kimberley Nunes on behalf of School of Information Technol and Elec Engineering