{"id":{"repo_id":"glasgow","oai_identifier":"oai:theses.gla.ac.uk:76486"},"canonical_url":"https://search.ndltd.org/etd/glasgow/oai:theses.gla.ac.uk:76486","repository":{"repo_id":"glasgow","name":"University of Glasgow","base_url":"https://theses.gla.ac.uk/cgi/oai2"},"display":{"title":"Jigsaws and Faster Fractal Pictures","abstract":"Today it is possible to express a wide range of images as attractors of Iterated Function Systems in the plane. An Iterated Function System, or IFS for short, is a finite collection of contractive affine transformations w1, w2,...,wN, while the attractor A is the limit under repeated application of the associated collage map W(E) = UiWi(E) for any compact set E - that is, Wn(E) → A [2, 12, 25, 26]. Since only 6N real numbers, known as the IFS code, are required to store the image, IFS's are now being widely used as a method of image compression [3, 4, 9] - leading to the need for algorithms which produce the attractor A quickly on a computer screen. In this thesis, we study one such algorithm - the Graphical Algorithm, or GA [5] -whose main characteristic is that maps are applied to points only after their coordinates have been rounded to integers. By introducing the concept of jigsaws of maps - where the jigsaw piece of an integer point (u, v) is the set of all integer points (x, y) such that w(x, y) rounds to (u, v) - and studying the properties of such sets, we reduce the time taken to produce an approximation to the attractor by up to a factor of N, making the GA as accurate as the Adaptive Cut Method (ACM) [11, 25, 26], and a frequently faster option than the popular Random Iteration Algorithm (RIA) [1, 2].","abstract_html":"Today it is possible to express a wide range of images as attractors of Iterated Function Systems in the plane. An Iterated Function System, or IFS for short, is a finite collection of contractive affine transformations w1, w2,...,wN, while the attractor A is the limit under repeated application of the associated collage map W(E) = UiWi(E) for any compact set E - that is, Wn(E) → A [2, 12, 25, 26]. Since only 6N real numbers, known as the IFS code, are required to store the image, IFS&#x27;s are now being widely used as a method of image compression [3, 4, 9] - leading to the need for algorithms which produce the attractor A quickly on a computer screen. In this thesis, we study one such algorithm - the Graphical Algorithm, or GA [5] -whose main characteristic is that maps are applied to points only after their coordinates have been rounded to integers. By introducing the concept of jigsaws of maps - where the jigsaw piece of an integer point (u, v) is the set of all integer points (x, y) such that w(x, y) rounds to (u, v) - and studying the properties of such sets, we reduce the time taken to produce an approximation to the attractor by up to a factor of N, making the GA as accurate as the Adaptive Cut Method (ACM) [11, 25, 26], and a frequently faster option than the popular Random Iteration Algorithm (RIA) [1, 2].","abstract_has_math":false,"creators":["Menzies, Lindsey"],"institution":"University of Glasgow","degree_name":null,"degree_level":"PhD","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1997,"date_issued":"1997","date_published":"1997","updated_at":"2026-11-19T08:31:13Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"https://theses.gla.ac.uk/76486/1/13834268.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://theses.gla.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Atheses.gla.ac.uk%3A76486","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Menzies, Lindsey"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1997"]},{"key":"dc:date.issued","label":"Date","values":["1997"]},{"key":"dc:publisher.commercial","label":"Dc Publisher Commercial","values":["ProQuest Dissertations & Theses,"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Mathematics."]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Glasgow"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://theses.gla.ac.uk/76486/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["PhD"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://theses.gla.ac.uk/76486/1/13834268.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Today it is possible to express a wide range of images as attractors of Iterated Function Systems in the plane. An Iterated Function System, or IFS for short, is a finite collection of contractive affine transformations w1, w2,...,wN, while the attractor A is the limit under repeated application of the associated collage map W(E) = UiWi(E) for any compact set E - that is, Wn(E) → A [2, 12, 25, 26]. Since only 6N real numbers, known as the IFS code, are required to store the image, IFS's are now being widely used as a method of image compression [3, 4, 9] - leading to the need for algorithms which produce the attractor A quickly on a computer screen. In this thesis, we study one such algorithm - the Graphical Algorithm, or GA [5] -whose main characteristic is that maps are applied to points only after their coordinates have been rounded to integers. By introducing the concept of jigsaws of maps - where the jigsaw piece of an integer point (u, v) is the set of all integer points (x, y) such that w(x, y) rounds to (u, v) - and studying the properties of such sets, we reduce the time taken to produce an approximation to the attractor by up to a factor of N, making the GA as accurate as the Adaptive Cut Method (ACM) [11, 25, 26], and a frequently faster option than the popular Random Iteration Algorithm (RIA) [1, 2]."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["Jigsaws and Faster Fractal Pictures"]}]}],"canonical_facts":{"dc:creator":["Menzies, Lindsey"],"dc:date":["1997"],"dc:date.issued":["1997"],"dc:description.abstract":["Today it is possible to express a wide range of images as attractors of Iterated Function Systems in the plane. An Iterated Function System, or IFS for short, is a finite collection of contractive affine transformations w1, w2,...,wN, while the attractor A is the limit under repeated application of the associated collage map W(E) = UiWi(E) for any compact set E - that is, Wn(E) → A [2, 12, 25, 26]. Since only 6N real numbers, known as the IFS code, are required to store the image, IFS's are now being widely used as a method of image compression [3, 4, 9] - leading to the need for algorithms which produce the attractor A quickly on a computer screen. In this thesis, we study one such algorithm - the Graphical Algorithm, or GA [5] -whose main characteristic is that maps are applied to points only after their coordinates have been rounded to integers. By introducing the concept of jigsaws of maps - where the jigsaw piece of an integer point (u, v) is the set of all integer points (x, y) such that w(x, y) rounds to (u, v) - and studying the properties of such sets, we reduce the time taken to produce an approximation to the attractor by up to a factor of N, making the GA as accurate as the Adaptive Cut Method (ACM) [11, 25, 26], and a frequently faster option than the popular Random Iteration Algorithm (RIA) [1, 2]."],"dc:format":["application/pdf"],"dc:identifier.uri":["https://theses.gla.ac.uk/76486/1/13834268.pdf"],"dc:language":["en"],"dc:publisher.commercial":["ProQuest Dissertations & Theses,"],"dc:publisher.department":["Department of Mathematics."],"dc:publisher.institution":["University of Glasgow"],"dc:relation.isreferencedby":["https://theses.gla.ac.uk/76486/"],"dcterms:accessrights":["public"],"dc:title":["Jigsaws and Faster Fractal Pictures"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["PhD"]},"updated_at":"2026-11-19T08:31:13Z"}