{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/11990"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/11990","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Shape Approximation of Printed Images in VLSI Design","abstract":"Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices. For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.","abstract_html":"Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices. For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.","abstract_has_math":false,"creators":["Han, Khine"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Wong, Martin D.F."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-06-01T16:07:27Z","date_published":"2009-06-01T16:07:27Z","updated_at":"2026-07-22T22:24:52Z","subjects":["vlsi","polygon","approximation"],"languages":[],"rights":["Copyright 2009 Khine Han"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/11990","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D.F."]},{"key":"dc:creator","label":"Author","values":["Han, Khine"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-06-01T16:07:27Z","2011-06-02T10:00:09Z","2009-5"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["vlsi","polygon","approximation"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2009 Khine Han"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/11990"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices. For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.","Item deposited via ETD process 2009-06-01.","Made available in DSpace on 2009-06-01T16:07:27Z (GMT). No. of bitstreams: 2 license.txt: 4057 bytes, checksum: e77b8237c83ac5573b98da075498a707 (MD5) Han_Khine.pdf: 902033 bytes, checksum: 8efa7e440ef31d5adf6c6bf4d9d3679c (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Timothy Donohue (tdonohue@illinois.edu) on 2009-06-01T16:07:37Z Item is restricted until 2011-06-01T16:07:37Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2011-06-02T10:00:09Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Han_Khine.pdf.txt: 81062 bytes, checksum: 08a53bcc23f70a2205794fe4dcd454b3 (MD5) license.txt: 4057 bytes, checksum: e77b8237c83ac5573b98da075498a707 (MD5) Han_Khine.pdf: 902033 bytes, checksum: 8efa7e440ef31d5adf6c6bf4d9d3679c (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2011-06-02T10:00:09Z"]},{"key":"dc:title","label":"Title","values":["Shape Approximation of Printed Images in VLSI Design"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D.F."],"dc:creator":["Han, Khine"],"dc:date":["2009-06-01T16:07:27Z","2011-06-02T10:00:09Z","2009-5"],"dc:description":["Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices. For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.","Item deposited via ETD process 2009-06-01.","Made available in DSpace on 2009-06-01T16:07:27Z (GMT). No. of bitstreams: 2 license.txt: 4057 bytes, checksum: e77b8237c83ac5573b98da075498a707 (MD5) Han_Khine.pdf: 902033 bytes, checksum: 8efa7e440ef31d5adf6c6bf4d9d3679c (MD5)","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Timothy Donohue (tdonohue@illinois.edu) on 2009-06-01T16:07:37Z Item is restricted until 2011-06-01T16:07:37Z","Item reinstated by Sarah Shreeves (sshreeve@illinois.edu) on 2011-06-02T10:00:09Z Item was in collections: Dissertations and Theses - Electrical and Computer Engineering (ID: 446) University of Illinois Dissertations and Theses (ID: 204) No. of bitstreams: 3 Han_Khine.pdf.txt: 81062 bytes, checksum: 08a53bcc23f70a2205794fe4dcd454b3 (MD5) license.txt: 4057 bytes, checksum: e77b8237c83ac5573b98da075498a707 (MD5) Han_Khine.pdf: 902033 bytes, checksum: 8efa7e440ef31d5adf6c6bf4d9d3679c (MD5)","Item released from any restrictions by Sarah Shreeves (sshreeve@illinois.edu) on 2011-06-02T10:00:09Z"],"dc:identifier":["http://hdl.handle.net/2142/11990"],"dc:rights":["Copyright 2009 Khine Han"],"dc:subject":["vlsi","polygon","approximation"],"dc:title":["Shape Approximation of Printed Images in VLSI Design"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}