Skip to main content
SpringerLink
Log in

Connectivity Graphs of Uncertainty Regions

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty, each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty, the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Notes

  1. We remark that for lists \({\mathcal {L}}\) and \({\mathcal {L}}'\) for two different spanning trees with two different sets of points on the segments, it is possible that \({\mathcal {L}} = {\mathcal {L}}'\), so that optimum solutions that permit minimum solutions trees are in general not unique.

  2. The descriptions are evident from Fig. 13, except perhaps the difference between c.1b and c.2. These are distinguished by the fact that \(f_{p_r}\) lies outside the semi-disc for c.1b, and inside the semi-disc for c.2, where p is \(p_\ell \) or \(p_r\), as appropriate.

  3. Count the number of ordered I-subsets of k segments by \(\sum _{i=1}^k k!/(k-i)!\), and multiply these by the \((n^2+n+1)\) to count ways that \(E_1\) and \(E_m\) might be points.

References

  1. Abellanas, M., Hurtado, F., Ramos, P.: Structural tolerance and Delaunay triangulation. Inf. Process. Lett. 71, 221–227 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alt, H., Arkin, E., Brönnimann, H., Erickson, J., Fekete, S., Knauer, C., Lenchner, J., Mitchell, J., Whittlesey, K.: Minimum-cost coverage of point sets by disks. In: Proceedings of the 22nd ACM Symposium on Computational Geometry (SoCG), pp. 449–458 (2006)

  3. Arkin, E.M., Dieckmann, C., Knauer, C., Mitchell, J.S.B., Polishchuk, V., Schlipf, L., Yang, S.: Convex transversals. In: Proceedings of the 12th International Symposium on Algorithms and Data Structures (WADS), pp. 49–60 (2011)

  4. Arkin, E.M., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. Discrete Appl. Math. 55(3), 197–218 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Chambers, E.W., Erickson, A., Fekete, S.P., Lenchner, J., Sember, J., Srinivasan, V., Stege, U., Stolpner, S., Weibel, C., Whitesides, S.: Connectivity graphs of uncertainty regions. In: 21st International Symposium on Algorithms and Computation (ISAAC), number 5307 in Springer LNCS, pp. 434–445 (2010)

  6. Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Technical Report TR00-054, Electronic Colloquium on Computational Complexity (2000)

  7. de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. J. Algorithms 57(1), 22–36 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  8. Ding, H., Xu, J.: Solving the chromatic cone clustering problem via minimum spanning sphere. In: 38th International Colloquium on Automata, Languages and Programming (ICALP), volume 6755 of Springer LNCS, pp. 773–784 (2011)

  9. Disser, Y., Mihalák, M., Montanari, S.: Max shortest path for imprecise points. In: 31st European Workshop on Computational Geometry, pp. 184–187 (2015)

  10. Disser, Y., Mihalák, M., Montanari, S., Widmayer, P.: Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods. In: Proceedings of the 3rd International Symposium on Combinatorial Optimization (ISCO), pp. 208–220 (2014)

  11. Dorrigiv, R., Fraser, R., He, M., Kamali, S., Kawamura, A., López-Ortiz, A., Seco, D.: On minimum- and maximum-weight minimum spanning trees with neighborhoods. In: Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA), pp. 93–106 (2012)

  12. Dror, M., Efrat, A., Lubiw, A., Mitchell, J.S.B.: Touring a sequence of polygons. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), pp. 473–482 (2003)

  13. Duchet, P., Hamidoune, Y.O., Vergnas, M.L., Meyniel, H.: Representing a planar graph by vertical lines joining different levels. Discrete Math. 46(3), 319–321 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  14. Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. In: Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 38–46 (2001)

  15. Fiala, J., Kratochvíl, J., Proskurowski, A.: Systems of distant representatives. Discrete Appl. Math. 145(2), 306–316 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fuchs, B.: On the hardness of range assignment problems. In: Proceedings of the 6th Italian Conference on Algorithms and Complecity (CIAC), pp. 127–138 (2006)

  17. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)

    MATH  Google Scholar 

  18. Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nord. J. Comput. 6(4), 469–488 (1999)

    MathSciNet  MATH  Google Scholar 

  19. Lev-Tov, N., Peleg, D.: Exact algorithms and approximation schemes for base station placement problems. In: Proceedings of the 8th Scandinavian Workshop Algorithm Theory (SWAT), pp. 90–99 (2002)

  20. Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Comput. Netw. 47(4), 489–501 (2005)

    Article  MATH  Google Scholar 

  21. Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  22. Löffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56, 235–269 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  23. Löffler, M., van Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. Theory Appl. 43, 419–433 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  24. Mata, C., Mitchell, J.: Approximation algorithms for geometric tour and network design problems. In: Proceedings of the 11th ACM Symposium on Computational Geometry (SoCG), pp. 360–369 (1995)

  25. Mitchell, J.S.B.: A PTAS for TSP with neighborhoods among fat regions in the plane. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11–18 (2007)

  26. Pan, X., Li, F., Klette, R.: Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons. In: Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG), pp. 175–178 (2010)

  27. Parker, G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesman problem. Oper. Res. Lett. 2(6), 269–272 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  28. Rosenstiehl, P., Tarjan, R.E.: Rectilinear planar layouts and bipolar orientations of planar graphs. Discrete Comput. Geom. 1, 343–353 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yang, Y., Lin, M., Xu, J., Xie, Y.: Minimum spanning tree with neighborhoods. In: Proceedings of the 3rd Conference on Algorithmic Aspects on Information and Management (AAIM), pp. 306–316. Springer, Berlin, Heidelberg (2007)

Download references

Acknowledgments

We are grateful for two Bellairs workshops supporting this research: the 8th and 9th McGill-INRIA-UVictoria Workshop on Computational Geometry in 2009 and 2010. We also thank the anonymous reviewers for many helpful and constructive comments that greatly helped to improve the overall presentation. We also acknowledge financial support by a number of different agencies, as follows. Erin Chambers was supported by NSF Grants CCF 1054779 and IIS 1319573. Alejandro Erickson was supported by the EPSRC, Grant No. EP/K015680/1. Ulrike Stege was supported by an NSERC Discovery Grant. Svetlana Stolpner was supported by the Fonds québécois de la recherche sur la nature et les technologies (FQRNT). Venkatesh Srinivasan was supported by an NSERC Discovery Grant. Sue Whitesides was supported by an NSERC Discovery Grant.

Author information

Authors and Affiliations

  1. Department of Computer Science, St. Louis University, St. Louis, MO, USA

    Erin Chambers

  2. School of Engineering and Computing Sciences, Durham University, Durham, UK

    Alejandro Erickson

  3. Department of Computer Science, Braunschweig University of Technology, Braunschweig, Germany

    Sándor P. Fekete

  4. IBM Research Africa, Nairobi, Kenya

    Jonathan Lenchner

  5. Department of Computer Science, University of British Columbia, Vancouver, BC, Canada

    Jeff Sember

  6. Department of Computer Science, University of Victoria, Victoria, BC, Canada

    Venkatesh Srinivasan, Ulrike Stege & Sue Whitesides

  7. A.U.G. Signals Ltd., Toronto, Canada

    Svetlana Stolpner

  8. Google, Zurich, Switzerland

    Christophe Weibel

Authors
  1. Erin Chambers
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alejandro Erickson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sándor P. Fekete
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jonathan Lenchner
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Jeff Sember
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Venkatesh Srinivasan
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Ulrike Stege
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Svetlana Stolpner
    View author publications

    You can also search for this author in PubMed Google Scholar

  9. Christophe Weibel
    View author publications

    You can also search for this author in PubMed Google Scholar

  10. Sue Whitesides
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sándor P. Fekete.

Additional information

A preliminary extended abstract summarizing parts of this paper appears in [5].

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chambers, E., Erickson, A., Fekete, S.P. et al. Connectivity Graphs of Uncertainty Regions. Algorithmica 78, 990–1019 (2017). https://doi.org/10.1007/s00453-016-0191-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0191-2

Keywords

Search

Navigation