Uncertain Points in Trees: Covering and Centering Problems
Explore the challenges of covering uncertain points in trees and solving centering problems efficiently. Discover the k-center problem's novel solutions and related research works in this area. Our findings introduce a new perspective on optimizing the placement of centers for uncertain points on trees.
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. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
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.
E N D
Presentation Transcript
Covering Uncertain Points in a Tree Haitao Wang and Jingru Zhang Utah State University WADS 2017, St. John s, Canada
An uncertain point in a tree T An uncertain point ??has multiple possible locations on T with probabilities ??2 0.2 ??1 0.4 0.3 ??5 ??4 0.1 0.1 ??3
An uncertain point The expected distance from ?? to a point x is ? ?? ??,? = ?? ??? ?(?,???) ?=1 ??3 ??3 x ??2 ??5 ??1 ??2 ??5 ??1 ??4 ??4
Problem definition Input: a tree T a set ? of nuncertain points and each ??has ?? locations a covering range ? Goal: Find a set ? of a minimum number of centers on T such that max 1 ? ???(??,?) ? where ?? ??,? = min ? ???(??,?) T ? = ?1,?2 ?2 ?1 ?1 ---- ?2 ---- ?3 ----
An application The k-center of uncertain points on a tree Input: a tree T and a set ? of uncertain points Goal: Find a set ? of at most k centers to minimize max 1 ? ???(??,?)
Related works Covering certain points in a tree: Time: ? ? --- O. Kariv and S. Hakimi (1979) The k-center problem of uncertain points on a line: Time: ? ??log?? + ?log?log? --- Wang and Zhang (2014) The one-center problem of uncertain points in a tree: Time: ? ?? --- Wang and Zhang (2015)
Our result The problem has not been studied before Our result: ?( ? + ? log?2) where ? is the number of locations of all uncertain points The k-center problem: O(|T|+n2 log n log M + M log3 M)
Problem definition Input: a tree T a set ? of nuncertain points and each ??with ?? locations a covering range ? Goal: Find a set ? of a minimum number of centers on T such that max 1 ? ???(??,?) ? T ? = ?1,?2 ?2 ?1 ?1 ---- ?2 ---- ?3 ----
The Median ?? of ?? The median ??of an uncertain point ?? is a vertex of T such that ?? ?,?? is minimized for all ? ?. ? ??1 ??2 ?? ??3 ??5 ??4 ?? ??,?? ?? ?,?? for all ? ? Observation: ?? ?,?? is monotonically increasing if x is moving away from pi
The medians-spanning tree The Medians-Spanning Tree ?? is the minimum connected subtree of Tthat spans all medians. ?? ?6 ? ?3 ?1 ?2 ?5 ?4
An observation ? All centers are in the medians-spanning tree of T ?? ?1 ?2 ?3 ?1 ?2 ?5 ?4
A greedy algorithm Place centers on ?? from bottom to top in the post-order traversal ?? ? --- root of ?? ?6 Initially, all medians are active. ? ?7 ?3 ?1 ?8 ?2 ?4 ?10 ?9 ?5 Deactivation: make medians whose uncertain points are covered by ? inactive
Processing a leaf Test whether a center is necessary on e for active ?? Compute c on ?(??,r) with ?? ?,?i = ? ? ?? ?(??,r) c is on e? Y N ?? ?,?i = ? ? Put a center at c for?? ?? served by a center not on e ? e ?? Report all uncertain points covered by ? ?? ??+1 c --- a candidate center Deactivation
Processing an internal node Test whether a center is necessary on e for active ??1, ??2, , ??? Data Structure ?1 Range-status-query Check whether ?v has active medians ? ?? ?(v,r) Y Data Structure ?2 Candidate-center-query Compute c on ?(v,r) with max Candidate center ? ?1 ? ???? ?,?i = ? ? e c is on e? v Data Structure ?3 Coverage-report-query N Y ?v Severed by a center not on e Report all uncertain points covered by ? Active medians ??1, ??2, , ??? Deactivation
Designing data structures---Major challenge Range-status query Preprocessing time Deletion Data Structure ?1 ?(?) ?(log?) ?(log?) Candidate-center- query Preprocessing time Deletion Data Structure ?2 ?(?log? + ?log2?) ?(log?) ?(log?) Preprocessing time ?(?log2?) Coverage-report-query Deletion Data Structure ?3 ?(?log? + log?log?) ?(??log?log2?) amortized
A connector-bounded centroid decomposition T ?2(?) ?1(?) ? c---the centroid of T max{ ?1? ,|?2(?)|} 2 ? 3 Decomposition Tree ? T c --- connector of ?1?and?2? ?1(?) ?2(?)
A connector-bounded centroid decomposition centroid ?? c ?2(?1) ?1(?) ? c ?2(?) ?1(?1) Decomposition Tree ? T ?1(?) ?2(?) c,?1--- connectors of ?1(?1) ?1--- connectors of ?2(?1) ?1(?1) ?2(?1)
A connector-bounded centroid decomposition ?1(?1) ?13(?4) Every subtree of ? has at most two connectors. ?1(?3) c ?? Decomposition Tree ? ?? ?11(?4) c ?c T ?? c ?12(?4) ?1(?) ?2(?) ?2(?3) ?4is the vertex such that ?1(?3) can be decomposed to three subtrees that contain c,?1, ?3, respectively. ?1(?1) ?2(?1) Decompose?1(?3) at ?4 ?12(?4) ?13(?4) ?2(?3) ?11(?4)
The decomposition tree of T Decomposition Tree T Each node ? of has at most four children ?1 ?2 Each node ? of --- A subtree ?(?) of ? Every ?(?) has at most two connectors ?3 ?5 ?4 ?6 Height: ?(log?) # of nodes: ?(?) ? ?(?)
Data structure ?3 for coverage-report-query Decomposition Tree For every node ? of ? ? --- List of all such ?? ? ?(? ) ??(?,??) --- Expected distance functions of all ?? ?(?) with respect to x ?(?) ? ?(?) ??= |? ? | Coverage-report-query in ?(?) --- ?(?log??+ log??) time ?? --- no location in ?(?) but in ?(? ) For any point x ?(?), Report all ?? ?(?) covered by ? --- all ?? ? ?with ??(?,??) ?
Coverage-report-query in ?(?) Observation: for each ?? ?(?) ?? ?,?? = ??(??+ ????+ ??) a plane in 3 ?2 ?(?) ?? for each ?? ?(?), ?? ?,?? ? defines a half-plane in the plane z =? ?? ?? ?1 ? = ??,?? Report all bounding lines above? --- report all ?? ?(?) with ?? ?,?? ??--- the distance of ? to the closest vertex ?? on ?(?1,?2) ??--- the distance of ?? to ?1 ?? ?,??1 ? ?? ?? ?,??2 ? L --- the set of ?? bounding lines ?? ?,??3 ? ? ??
Coverage-report-query in ?(?) ?2 ?(?) Report bounding lines of ? above ? Build half-plane range reporting data structure on ? in ?( ? ? time ?1 + ??log??) ? = ??,?? Half-plane range reporting query for ? ?(?) 1. Coverage-report-query in ?(?) --- ?(?log??+ log??) time Report all ?? ?(?) with ?? ?,?? for any ? ? ? 2. Removing any ?? from ?(?) --- ?(log??) time
Coverage-report-query on ?3 ?(?), ?(?),? ? Any point ? on T ? A path ? in ? ? log? nodes --- subtrees ?(?) Coverage-report-query at ? in every ?(?) ? Report all indices i with ??(?,??) ? --- ?(?log? + log?log?) time
Data structures Range-status query Preprocessing time Deletion Data Structure ?1 ?(?) ?(log?) ?(log?) Candidate-center- query Preprocessing time Deletion Data Structure ?2 ?(?log? + ?log2?) ?(log?) ?(log?) Preprocessing time ?(?log2?) Coverage-report-query Deletion Data Structure ?3 ?(?log? + log?log?) ?(??log?log?)
Thank you! Q&A
