{"id":{"repo_id":"utahstate","oai_identifier":"oai:digitalcommons.usu.edu:etd-9090"},"canonical_url":"https://search.ndltd.org/etd/utahstate/oai:digitalcommons.usu.edu:etd-9090","repository":{"repo_id":"utahstate","name":"Utah State University","base_url":"https://digitalcommons.usu.edu/do/oai/"},"display":{"title":"Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm","abstract":"Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site.","abstract_html":"Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site.","abstract_has_math":false,"creators":["Marsden, Daniel"],"institution":"Hosted by Utah State University Libraries","degree_name":"Master of Science (MS)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["John Edwards","Xiaojun Qi","Minghui Jiang"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:51:54Z","subjects":["Voronoi","Generalized Voronoi","Fortune","Sweep line","Algorithm","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/016f-c239"],"render_values":[{"text":"https://doi.org/10.26076/016f-c239","href":"https://doi.org/10.26076/016f-c239","code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usu.edu/etd/7947","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usu.edu/etd/7947","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usu.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usu.edu%3Aetd-9090","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["John Edwards","Xiaojun Qi","Minghui Jiang"]},{"key":"dc:creator","label":"Author","values":["Marsden, Daniel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2010-01-01T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2020-12-01T08:00:00Z"]},{"key":"dc:publisher","label":"Institution","values":["Hosted by Utah State University Libraries"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Voronoi","Generalized Voronoi","Fortune","Sweep line","Algorithm","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usu.edu/etd/7947"]},{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.26076/016f-c239"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site."]},{"key":"dc:title","label":"Title","values":["Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm"]}]}],"canonical_facts":{"dc:contributor":["John Edwards","Xiaojun Qi","Minghui Jiang"],"dc:creator":["Marsden, Daniel"],"dc:date.available":["2010-01-01T08:00:00Z"],"dc:date.created":["2020-12-01T08:00:00Z"],"dc:description.abstract":["Voronoi Diagrams can provide useful spatial information. Little work has been done on computing exact Voronoi Diagrams when the sites are more complex than a point. We introduce a technique that measures the exact Generalized Voronoi Diagram from points, line segments and, connected lines including lines that connect to form simple polygons. Our technique is an extension of Fortune’s method. Our approach treats connected lines (or polygons) as a single site."],"dc:identifier":["https://digitalcommons.usu.edu/etd/7947"],"dc:identifier.doi":["https://doi.org/10.26076/016f-c239"],"dc:publisher":["Hosted by Utah State University Libraries"],"dc:subject":["Voronoi","Generalized Voronoi","Fortune","Sweep line","Algorithm","Computer Sciences"],"dc:title":["Exact Generalized Voronoi Diagram Computation using a Sweepline Algorithm"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:51:54Z"}