Skip to main content
SpringerLink
Log in

Connected component and simple polygon intersection searching

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

Efficient data structures are given for the following two query problems: (i) preprocess a setP of simple polygons with a total ofn edges, so that all polygons ofP intersected by a query segment can be reported efficiently, and (ii) preprocess a setS ofn segments, so that the connected components of the arrangement ofS intersected by a query segment can be reported quickly. In these problems we do not want to return the polygons or connected components explicitly (i.e., we do not wish to report the segments defining the polygon, or the segments lying in the connected components). Instead, we assume that the polygons (or connected components) are labeled and we just want to report their labels. We present data structures of sizeO(n 1+ε) that can answer a query in timeO(n 1+ε+k), wherek is the output size. If the edges ofP (or the segments inS) are orthogonal, the query time can be improved toO(logn+k) usingO(n logn) space. We also present data structures that can maintain the connected components as we insert new segments. For arbitrary segments the amortized update and query time areO(n 1/2+ε) andO(n 1/2+ε+k), respectively, and the space used by the data structure isO(n 1+ε. If we allowO(n 4/3+ε space, the amortized update and query time can be improved toO(n 1/3+ε andO(n 1/3+ε+k, respectively. For orthogonal segments the amortized update and query time areO(log2 n) andO(log2 n+klogn), and the space used by the data structure isO (n logn). Some other related results are also mentioned.

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

Similar content being viewed by others

References

  1. P. K. Agarwal, Partitioning Arrangements of Lines: II. Applications,Discrete Comput. Geom. 5 (1991), 533–573.

    Google Scholar 

  2. P. K. Agarwal, Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number,SIAM J. Comput. 21 (1992), 540–570.

    Article  Google Scholar 

  3. P. K. Agarwal, M. van Kreveld, and M. Overmars, Intersection Queries in Curved Objects,J. Algorithms 15 (1993), 229–266.

    Article  Google Scholar 

  4. P. K. Agarwal and M. Sharir, Applications of aNew Space Partitioning Technique,Discrete Comp. Geom. 9 (1993), 11–38.

    Google Scholar 

  5. B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, Improved Bounds on the Complexity of Many Faces in Arrangements of Segments,Combinatorica 12 (1992), 261–274.

    Article  Google Scholar 

  6. R. Bar Yehuda and S. Fogel, Good Splitters with Applications to Ray Shooting,Algorithmica 11 (1994), 133–145.

    Article  Google Scholar 

  7. B. Chazelle, M. Sharir, and E. Welzl, Quasi-Optimal Upper Bounds for Simplex Range Searching and New Zone Theorems,Algorithmica 8 (1992), 407–430.

    Article  Google Scholar 

  8. S. W. Cheng and R. Janardan, Algorithms for Ray-Shooting and Intersection Searching,J. Algorithms 13 (1992), 670–692.

    Article  Google Scholar 

  9. T. H. Cormen, C. E. Leiserson, and R. L. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA, 1990.

    Google Scholar 

  10. M. Dillencourt, H. Samet, and M. Tammiuen, A General Approach to Connected Component Labeling for Arbitrary Image Representation,J. Assoc. Comput. Mach. 39 (1992), 253–280.

    MathSciNet  Google Scholar 

  11. D. P. Dobkin and H. Edelsbrunner, Space Searching for Intersecting Objects,J. Algorithms 8 (1987), 348–361.

    Article  Google Scholar 

  12. H. Edelsbrunner,Algorithms in Combinatorial Geometry, Springer-Verlag, Berlin, 1987.

    Google Scholar 

  13. L. Guibas, Personal communication.

  14. L. Guibas, M. Overmars, and M. Sharir, Ray Shooting, Implicit Point Location, and Related Queries in Arrangements of Segments, Techn. Rep. No. 433, New York University, 1989.

  15. J. Gupta, R. Janardan, and M. Smid, Further Results on Generalized Intersection Searching Problems: Counting, Reporting and Dynamization,Proc. 3rd Workshop on Algorithms and Data Structures (1993), Lecture Notes in Computer Science, Vol. 709, Springer-Verlag, Berlin, pp. 361–372.

    Google Scholar 

  16. J. Gupta, R. Janardan, and M. Smid, Efficient Algorithms for Generalized Intersection Searching on Non-Iso-Oriented Objects,Proc. 10th ACM Symposium on Computational Geometry (1994), pp. 369–378.

  17. J. Gupta, R. Janardan, and M. Smid, On Intersection Searching Involving Curved Objects,Proc. 4th Scand. Workshop on Algorithms Theory (1994), Lecture Notes in Computer Science, Vol. 824, Springer-Verlag, Berlin, pp. 183–194.

    Google Scholar 

  18. H. Imai and T. Asano, Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane,J. Algorithms 4 (1984), 310–323.

    Article  Google Scholar 

  19. R. Janardan and M. Lopez, Generalized Intersection Searching Problems,Internat. J. Comput. Geom. Appl. 3 (1993), 39–70.

    Article  Google Scholar 

  20. J. Matoušek, Range Searching with Efficient Hierarchical Cuttings,Discrete Comput. Geom. 10 (1993), 157–182.

    Google Scholar 

  21. K. Mehlhorn,Data Structures and Algorithms 3: Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984.

    Google Scholar 

  22. J. Nievergelt and P. Widmayer, Guard Files: Stabbing and Intersection Queries on Fat Spatial Objects,Comput. J. 36 (1993), 107–116.

    Article  Google Scholar 

  23. M. H. Overmars,The Design of Dynamic Data Structures, Lecture Notes in Computer Science, Vol. 156, Springer-Verlag, Berlin, 1983.

    Google Scholar 

  24. M. H. Overmars, H. Schipper, and M. Sharir, Storing Line Segments in Partition Trees, BIT 30 (1990), 385–403.

    Google Scholar 

  25. F. P. Preparata, A Real Time Algorithm for Convex Hull,Comm. ACM 22 (1979), 402–405.

    Article  Google Scholar 

  26. F. P. Preparata and M. I. Shamos,Computational Geometry—an Introduction, Springer-Verlag, New York, 1985.

    Google Scholar 

  27. N. Sarnak and R. Tarjan, Planar Point Location Using Persistent Search Trees,Comm. ACM 29 (1986), 609–679.

    Article  Google Scholar 

  28. H. W. Schölten and M. H. Overmars, General Methods for Adding Range Restrictions to Decomposable Searching Problems,J. Symbolic Comput. 7 (1989), 1–10.

    Google Scholar 

  29. M. Sharir and P. Agarwal,Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, New York, 1995.

    Google Scholar 

  30. R. E. Tarjan, Amortized Time Complexity,SIAM J. Discrete Math. 6 (1985), 306–318.

    Google Scholar 

  31. D. E. Willard and G. S. Lueker, Adding Range Restriction Capability to Dynamic Data Structures,J. Assoc. Comput. Mach. 32 (1985), 597–617.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Duke University, P.O. Box 90129, 27708-0129, Durham, NC, USA

    P. K. Agarwal

  2. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, The Netherlands

    M. van Kreveld

Authors
  1. P. K. Agarwal
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. van Kreveld
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by B. Chazelle.

Part of this work was done while the second author was visiting the first author on a grant by the Dutch Organization for Scientific Research (N.W.O.). The research of the second author was also supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The research of the first author was supported by National Science Foundation Grant CCR-91-06514.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Agarwal, P.K., van Kreveld, M. Connected component and simple polygon intersection searching. Algorithmica 15, 626–660 (1996). https://doi.org/10.1007/BF01940884

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01940884

Key words

Search

Navigation