Optimized Algorithm for Minimum Link Rectilinear Paths in Triangulated Domains
This study presents an optimal algorithm for finding the minimum link rectilinear paths in triangulated domains, focusing on solving the minimum-link path problem efficiently. The research covers various scenarios, such as general polygonal domains and rectilinear cases, proposing new algorithms and time-space complexities for optimal pathfinding. Key highlights include a detailed comparison with previous works and the development of data structures for efficiently answering single-source queries.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
An Optimal Algorithm for Minimum An Optimal Algorithm for Minimum- - Link Rectilinear Paths in Link Rectilinear Paths in Triangulated Rectilinear Domains Triangulated Rectilinear Domains Joseph S.B. Mitchell, Stony Brook University Valentin Polishchuk, Link ping University Mikko Sysikaski, Google Zurich Haitao Wang, Utah State University ICALP 2015
A general polygonal domain A general polygonal domain Input: a simple polygon P with some polygons (holes or obstacles) inside, and two points s and t Output: a path from s to t in P s t
Minimum Minimum- -link paths link paths Making a turn in the s-t path is too expensive Output: a minimum-link path from s to t an s-t path of minimum number of edges (links) s t
The rectilinear case of minimum The rectilinear case of minimum- -link path problem path problem link Each polygon edge is either horizontal or vertical Each edge of the sought s-t path is also either horizontal or vertical t s
The rectilinear minimum The rectilinear minimum- -link path problem problem link path Input: a rectilinear domain P of n vertices and h holes, and s and t Output: a rectilinear minimum-link s-t path t n = 39 h = 3 s
Previous work and our result Previous work and our result The general case O(n2 (n) log2n) time, Mitchell, Rote, and Woeginger 92 The rectilinear case O(n log n) time and O(n log n) space, Imai and Asano 86 O(n log n) time and O(n) space, SSO 87 , DN 91 , MPS 14 (n + h log h) time lower bound, DN91 , MSD 00 Our result: O(n + h log h) time and O(n) space, with a given triangulation of P triangulating P O(n + h log1+ h) time, Bar-Yehuda and Chazelle 94
Our result: answering single Our result: answering single- -source queries queries source Build a data structure in O(n + h log h) time and O(n) space for s, to answer the queries: given any query point t, compute the link distance (the number of links of the rectilinear minimum-link s-t path) in O(log n) time report the actual path in additional time linear in the link distance
Outline Outline The previous work: Das and Narasimhan, 91 Our improvement based on their work
Four types of rectilinear paths Four types of rectilinear paths Any rectilinear s-t path can be a vertical-start-vertical-end path, or v-v path a vertical-start-horizontal-end path, or v-h path a horizontal-start-vertical-end path, or h-v path a horizontal-start-horizontal-end path, or h-h path t t t t s s s s v-v path v-h path h-v path h-h path
Computing a minimum Computing a minimum- -link path link path Compute the four paths: a minimum-link v-v path a minimum-link v-h path a minimum-link h-v path a minimum-link h-h path Return the one with the minimum link distance as the solution by a v-v link distance map by a v-h map by an h-v map by an h-h map
Computing a v Computing a v- -v map The vertical decomposition of P, VD(P) Extend each vertical edge until the boundary of P Each extension segment is called a diagonal Computing VD(P) is equivalent to triangulating P v map
Computing a v Computing a v- -v map (cont.) v map (cont.) VD(P) is our v-v map. Why? Observation: For each cell, all points in the cell have the same v-v link distance to s t s
Computing a v Computing a v- -v map (cont.) v map (cont.) Label each cell with its v-v link distance to s 5 5 5 5 5 5 t 5 5 5 5 7 5 7 5 3 s 3 3 3 3 3 3 3 1
Labelling the diagonals (the vertical Labelling the diagonals (the vertical extensions) extensions) Initially, label the diagonal dsthrough s by 1 Put a light source on the entire dsgenerating light beams towards leftwards and rightwards any diagonals illuminated by dswill get label 3 5 3
The algorithm in the previous work The algorithm in the previous work In the i-th round, for i = 0, 1, 2, 3 .. Finds a set Viof diagonals and label them 2i + 1 What is Vi? If we put light sources on all diagonals of Vi-1, then Viconsists of all new diagonals that can be illuminated Two sweeping procedures: left-sweep and right-sweep A heap is used to guide the sweeping such that the diagonals are processed by their x-coordinates The sweeping is controlled in a global manner O(n log n) time in total
Our improvement: using a Our improvement: using a corridor structure structure corridor Consider the dual graph G of the VD(P) Keep removing the degree-one nodes from G Keep contracting the degree-two nodes
Our improvement: using a Our improvement: using a corridor structure structure corridor The remaining graph G is called corridor graph Each vertex of G corresponds to a junction cell Each edge of G corresponds to a corridor
Our improvement: using a Our improvement: using a corridor structure structure (cont.) (cont.) corridor Each corridor is a simple rectilinear polygon Each corridor has two doors connecting with its neighboring junction cells
Our improvement: using a Our improvement: using a corridor structure structure (cont.) (cont.) There are O(h) junction cells and O(h) corridors Incorporating the source point s s is considered as a special vertex of the corridor graph The diagonal dsis considered as a special junction cell corridor s
Our algorithm Our algorithm an overview an overview We use the same sweeping approach as before with the following differences The sweeping in the junction cells is controlled in a global manner, the same as before Once the sweeping enters into a corridor C through one of its doors, we sweep C in a local manner What is the benefit? The global sweeping is only on junction cells There are only O(h) junction cells O(h log h) time The local sweeping in each corridor can be processed in linear time since it is a simple polygon The total size of all corridors is O(n) O(n) time
Our algorithm Our algorithm a demonstration a demonstration 5 3 5 s 3 3 3 1
The sweeping in corridors The sweeping in corridors Suppose there are h1beams entering a corridor C through a door, and h2beams leaving C through the other door after the sweeping Our algorithm runs in O(|C| + (h1 h2) log h1) time The sum of the first term in the entire algorithm is O(n) The sum of the second term is O(h log h) h1= 5 h2= 2 C
Operations on beam sets on diagonals Operations on beam sets on diagonals Some beams may be terminated , narrowed A beam set may be split Beam sets may be merged
Thank you! Thank you!
