AbstractsComputer Science

This thesis considers the problem of preprocessing polygons with holes for efficient two-point Euclidean shortest path queries. Special attention is given to the 1999 paper “Two-Point Euclidean Shortest Path Queries in the Plane”, which sketched a number of solutions to the problem and whose results remain the best in the field. This thesis reviews four of the algorithms presented in the paper and fleshes them out when possible. Vain tiivistelmä. Opinnäytteiden arkistokappaleet ovat luettavissa Helsingin yliopiston kirjastossa. Hae HELKA-tietokannasta (http://www.helsinki.fi/helka/index.htm). Abstract only. The paper copy of the whole thesis is available for reading room use at the Helsinki University Library. Search HELKA online catalog (http://www.helsinki.fi/helka/index.htm). Endast avhandlingens sammandrag. Pappersexemplaret av hela avhandlingen finns för läsesalsbruk i Helsingfors universitets bibliotek. Sök i HELKA-databasen (http://www.helsinki.fi/helka/index.htm).