Weak Visibility Queries of Line Segments in Simple Polygons - Overview
This information discusses weak visibility queries of line segments in simple polygons, focusing on topics such as visibility of line segments, visibility polygons, visibility graphs, and related previous work on preprocessing and data structures for visibility queries in simple polygons.
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
Weak Visibility Queries of Line Weak Visibility Queries of Line Segments in Simple Polygons Segments in Simple Polygons Haitao Wang Utah State University ISAAC 2012 Joint work with Danny Z. Chen
Visibility Visibility p is visible to q p q
Visibility of line segments Visibility of line segments s q p Both p and q are (weakly) visible to s
(Weak) visibility polygons (Weak) visibility polygons The visibility polygon of s: the set of points visible to s s
Visibility polygons (cont.) Visibility polygons (cont.) s
Our problem: Our problem: visibility queries visibility queries Given a simple polygon P, design a data structure (or do preprocessing) For any query segment s in P, compute the visibility polygon of s Notation n: the size of P k: the size of the visibility polygon of s
Previous work (no preprocessing) Previous work (no preprocessing) A linear time algorithm (GHLMT 87 )
Previous work (with preprocessing) Previous work (with preprocessing) Data structures preprocessing time space Query time Bose et al. 02 O(n3log n) O(n3) O(klog n) Aronov et al. 02 O(n2log n) O(n2) O(klog2n) Bygi and Ghodsi 11 O(n3log n) O(n3) O(k+log n)
The visibility graph of P The visibility graph of P Connecting all visible pairs of vertices The size of the graph is O(n2)
Our results Our results Data structures Bose et al. 02 preprocessing time O(n3log n) space Query time O(n3) O(klog n) Aronov et al. 02 O(n2log n) O(n2) O(klog2n) Bygi and Ghodsi 11 Our Result 1 O(n3log n) O(n3) O(k+log n) O(K) O(K) O(klog n) Our Result 2 O(n3) O(n3) O(k+log n) Our recent result: O(n) O(n) O(k log n) K=O(n2): the size of the visibility graph of P
Computing the visibility polygon Computing the visibility polygon
Computing the visibility polygon Computing the visibility polygon q v u
Computing the visibility polygon Computing the visibility polygon q v u
Computing the visibility polygon Computing the visibility polygon critical constraints q v u
Computing the visibility polygon Computing the visibility polygon critical constraints The purple segments q v u Question: How to determine the critical constraints dynamically?
Observations: finding the critical Observations: finding the critical constraints dynamically constraints dynamically q v u
Our two approaches Our two approaches Determine critical constraints dynamically in the query algorithm Pre-compute the critical constraint arrangement in the preprocessing
The first approach: determine critical The first approach: determine critical constraints dynamically constraints dynamically Using visibility graphs (in the paper) Preprocessing time and space: O(K) Using a ray-rotating data structure (our recent result) Preprocessing time and space: O(n) Query determine each critical constraint in O(log n) time Total query time: O(klog n) The total number of critical constraints intersecting s is O(k)
The ray The ray- -rotating queries rotating queries Given a ray r with origin z in P, rotate r clockwise return the first vertex of P visible to z that will be hit by the ray r z Our result: with O(n) time preprocessing, each query can be answered in O(log n) time Interesting in its own right?
The second approach: pre The second approach: pre- -compute the critical constraint arrangement the critical constraint arrangement compute Preprocessing Compute all critical constraints explicitly O(n3) time and space Query Follow the query segment in the arrangement Query time: O(k+logn)
Critical constraint arrangement Critical constraint arrangement Each critical constraint is an extension of a visibility graph edge The number of critical constraints is O(n2) The size of the arrangement is O(n3)
Critical constraint arrangement Critical constraint arrangement Given a query segment s The complexity of all yellow cells are O(k) k: the size of the visibility polygon of s
The zone theorem of line segment The zone theorem of line segment arrangements in the plane arrangements in the plane A: the arrangement of m line segments for any other line segment s The zone Z(s): the set of all faces of A intersecting s The zone theorem: The complexity of Z(s): O(m (m)) (Edelsbrunner et al. 92)
The zone theorem of line segment The zone theorem of line segment arrangements in simple polygons arrangements in simple polygons A new question: What is the complexity of Z(s), if All segments of A are in a simple polygon P The endpoints of each segment in A are on the boundary of P Our answer: O(M) M: the number of segments of A intersecting Z(s)
Open problem Open problem Data structures preprocessing time O(n3log n) O(n2log n) space Query time Bose et al. 02 Aronov et al. 02 O(n3) O(n2) O(klog n) O(klog2n) Bygi and Ghodsi 11 O(n3log n) O(n3) O(k+log n) Our Recent Result O(n) O(n) O(klog n) Our Result 2 O(n3) O(n3) O(k+log n) Open problem: are there sub-cubic data structures for O(k + log n) time query?
Thank you Thank you Questions?
