A compact piecewise-linear Voronoi diagram for convex sites in the plane, or, Simple paths in a complex world

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.

Name thesis:degree_name

Master of Science - MSc

Level thesis:degree_level

master's

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

University of British Columbia

Year dc:date

1993

Author dc:creator

• McAllister, Michael

Statement 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.

Language dc:language

eng

Handle dc:identifier

http://hdl.handle.net/2429/2000

OAI identifier oai:identifier

oai:circle.library.ubc.ca:2429/2000