{"id":{"repo_id":"ubc","oai_identifier":"oai:circle.library.ubc.ca:2429/2000"},"canonical_url":"https://search.dev.ndltd.org/etd/ubc/oai:circle.library.ubc.ca:2429/2000","repository":{"repo_id":"ubc","name":"University of British Columbia","base_url":"http://circle.library.ubc.ca/oai/request"},"display":{"title":"A compact piecewise-linear Voronoi diagram for convex sites in the plane, or, Simple paths in a complex world","abstract":"In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using 0(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices given in standard representations, we compute this diagram optimally in 0(k log n) deterministic time for the Euclidean metric and in 0(k log n log m) deterministic time for the convex distance function defined by a convex m-gon.","abstract_html":"In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using 0(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices given in standard representations, we compute this diagram optimally in 0(k log n) deterministic time for the Euclidean metric and in 0(k log n log m) deterministic time for the convex distance function defined by a convex m-gon.","abstract_has_math":false,"creators":["McAllister, Michael"],"institution":"University of British Columbia","degree_name":"Master of Science - MSc","degree_level":"master's","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1993,"date_issued":"1993","date_published":"1993","updated_at":"2026-07-24T05:07:24Z","subjects":[],"languages":["eng"],"rights":["For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2429/2000","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["McAllister, Michael"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1993"]},{"key":"dc:publisher","label":"Institution","values":["University of British Columbia"]},{"key":"dc:type","label":"Dc Type","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["master's"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science - MSc"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of British Columbia"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2429/2000","http://circle.library.ubc.ca/bitstream/2429/2000/1/ubc_1993_fall_mcallister_michael.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using 0(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices given in standard representations, we compute this diagram optimally in 0(k log n) deterministic time for the Euclidean metric and in 0(k log n log m) deterministic time for the convex distance function defined by a convex m-gon."]},{"key":"dc:format","label":"Dc Format","values":["2594800","application/pdf"]},{"key":"dc:title","label":"Title","values":["A compact piecewise-linear Voronoi diagram for convex sites in the plane, or, Simple paths in a complex world"]}]}],"canonical_facts":{"dc:creator":["McAllister, Michael"],"dc:date":["1993"],"dc:description":["In the plane, the post-office problem, which asks for the closest site to a query site, and retraction motion planning, which asks for a one-dimensional retract of the free space of a robot, are both classically solved by computing a Voronoi diagram. When the sites are k disjoint convex sets, we give a compact representation of the Voronoi diagram, using 0(k) line segments, that is sufficient for logarithmic time post-office location queries and motion planning. If these sets are polygons with n total vertices given in standard representations, we compute this diagram optimally in 0(k log n) deterministic time for the Euclidean metric and in 0(k log n log m) deterministic time for the convex distance function defined by a convex m-gon."],"dc:format":["2594800","application/pdf"],"dc:identifier":["http://hdl.handle.net/2429/2000","http://circle.library.ubc.ca/bitstream/2429/2000/1/ubc_1993_fall_mcallister_michael.pdf"],"dc:language":["eng"],"dc:publisher":["University of British Columbia"],"dc:rights":["For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use."],"dc:title":["A compact piecewise-linear Voronoi diagram for convex sites in the plane, or, Simple paths in a complex world"],"dc:type":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["master's"],"thesis:degree_name":["Master of Science - MSc"],"thesis:institution_name":["University of British Columbia"]},"updated_at":"2026-07-24T05:07:24Z"}