Document Open Access Logo

Space-Efficient Plane-Sweep Algorithms

Authors Amr Elmasry, Frank Kammer

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.30.pdf
  • Filesize: 418 kB
  • 13 pages

Document Identifiers

Author Details

Amr Elmasry
Frank Kammer

Cite As Get BibTex

Amr Elmasry and Frank Kammer. Space-Efficient Plane-Sweep Algorithms. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.30

Abstract

We introduce space-efficient plane-sweep algorithms for basic planar geometric problems. It is assumed that the input is in a read-only array of n items and that the available workspace is Theta(s) bits, where lg n <= s <= n * lg n. Three techniques that can be used as general tools in different space-efficient algorithms are introduced and employed within our algorithms. In particular, we give an almost-optimal algorithm for finding the closest pair among a set of n points that runs in O(n^2 /s + n * lg s) time. We also give a simple algorithm to enumerate the intersections of n line segments that runs in O((n^2 /s^{2/3}) * lg s + k) time, where k is the number of intersections. The counting version can be solved in O((n^2/s^{2/3}) * lg s) time. When the segments are axis-parallel, we give an O((n^2/s) * lg^{4/3} s + n^{4/3} * lg^{1/3} n)-time algorithm that counts the intersections and an O((n^2/s) * lg s * lg lg s + n * lg s + k)-time algorithm that enumerates the intersections, where k is the number of intersections. We finally present an algorithm that runs in O((n^2 /s + n * lg s) * sqrt{(n/s) * lg n}) time to calculate Klee's measure of axis-parallel rectangles.

Subject Classification

Keywords
  • closest pair
  • line-segments intersection
  • Klee's measure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K. Agarwal. Partitioning arrangements of lines II: Applications. Discrete Comput. Geom., 5(6):533-573, 1990. Google Scholar
  2. Tetsuo Asano, Amr Elmasry, and Jyrki Katajainen. Priority queues and sorting for read-only data. In Proc. 10th International Conference on Theory and Applications of Models of Computation (TAMC 2013), volume 7876 of LNCS, pages 32-41, 2013. URL: http://dx.doi.org/10.1007/978-3-642-38236-9_4.
  3. Tetsuo Asano, Wolfgang Mulzer, Günter Rote, and Yajun Wang. Constant-work-space algorithms for geometric problems. J. Comput. Geom., 2(1):46-68, 2011. Google Scholar
  4. Ivan J. Balaban. An optimal algorithm for finding segments intersections. In Proc. 11th Symposium on Computational Geometry, pages 211-219, 1995. URL: http://dx.doi.org/10.1145/220279.220302.
  5. Paul Beame. A general sequential time-space tradeoff for finding unique elements. SIAM J. Comput., 20(2):270-277, 1991. URL: http://dx.doi.org/10.1137/0220017.
  6. Jon Louis Bentley. Algorithms for Klee’s rectangle problems, 1977. Unpublished manuscript. Google Scholar
  7. Jon Louis Bentley and Thomas Ottmann. Algorithms for reporting and counting geometric intersections. IEEE Trans. Computers, 28(9):643-647, 1979. URL: http://dx.doi.org/10.1109/TC.1979.1675432.
  8. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 2008. Google Scholar
  9. Timothy M. Chan. Closest-point problems simplified on the RAM. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), pages 472-473, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545444.
  10. Timothy M. Chan. Klee’s measure problem made easy. In Proc. 54th Anual IEEE Symposium on Foundations of Computer Science (FOCS 2013), pages 410-419, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.51.
  11. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comput. Geom., 9(2):145-158, 1993. Google Scholar
  12. David Clark. Compact Pat Trees. PhD thesis, University of Waterloo, Waterloo, Ontario, Canada, 1996. Google Scholar
  13. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  14. Omar Darwish and Amr Elmasry. Optimal time-space tradeoff for the 2D convex-hull problem. In Proc. 22nd Annual European Symposium on Algorithms (ESA 2014), volume 8737 of LNCS, pages 284-295, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_24.
  15. Amr Elmasry, Frank Kammer, and Torben Hagerup. Space-efficient basic graph algorithms. In Proc. 32nd Annual Symposium on Theoretical Aspects of Computer Science (STACS 2015), LIPIcs, pages 288-301, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.288.
  16. Greg N. Frederickson. Upper bounds for time-space trade-offs in sorting and selection. J. Comput. Syst. Sci., 34(1):19-26, 1987. URL: http://dx.doi.org/10.1016/0022-0000(87)90002-X.
  17. Matsuo Konagaya and Tetsuo Asano. Reporting all segment intersections using an arbitrary sized work space. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 96-A(6):1066-1071, 2013. URL: http://search.ieice.org/bin/summary.php?id=e96-a_6_1066.
  18. Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Time-space trade-offs for triangulations and Voronoi diagrams. In Proc. 14th Algorithms and Data Structures Symposium (WADS 2015), 2015. Google Scholar
  19. J. I. Munro and M. S. Paterson. Selection and sorting with limited storage. Theor. Comput. Sci., 12(3):315-323, 1980. URL: http://dx.doi.org/10.1016/0304-3975(80)90061-4.
  20. Mark H. Overmars and Chee-Keng Yap. New upper bounds in Klee’s measure problem (extended abstract). In Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), pages 550-556, 1988. URL: http://dx.doi.org/10.1109/SFCS.1988.21971.
  21. Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proc. 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1998), pages 264-268, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743455.
  22. Andrew Chi-Chih Yao. Near-optimal time-space tradeoff for element distinctness. SIAM J. Comput., 23(5):966-975, 1994. URL: http://dx.doi.org/10.1137/S0097539788148959.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact