Document Open Access Logo

Near-Optimal Algorithms for Point-Line Covering Problems

Authors Jianer Chen, Qin Huang, Iyad Kanj, Ge Xia

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.21.pdf
  • Filesize: 0.83 MB
  • 18 pages

Document Identifiers

Author Details

Jianer Chen
  • Department of Computer Science and Engineering, Texas A&M University, TX, USA
Qin Huang
  • Department of Computer Science and Engineering, Texas A&M University, TX, USA
Iyad Kanj
  • School of Computing, DePaul University, Chicago, IL, USA
Ge Xia
  • Department of Computer Science, Lafayette College, Easton, PA, USA

Cite As Get BibTex

Jianer Chen, Qin Huang, Iyad Kanj, and Ge Xia. Near-Optimal Algorithms for Point-Line Covering Problems. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.STACS.2022.21

Abstract

We study fundamental point-line covering problems in computational geometry, in which the input is a set S of points in the plane. The first is the Rich Lines problem, which asks for the set of all lines that each covers at least λ points from S, for a given integer parameter λ ≥ 2; this problem subsumes the 3-Points-on-Line problem and the Exact Fitting problem, which - the latter - asks for a line containing the maximum number of points. The second is the NP-hard problem Line Cover, which asks for a set of k lines that cover the points of S, for a given parameter k ∈ ℕ. Both problems have been extensively studied. In particular, the Rich Lines problem is a fundamental problem whose solution serves as a building block for several algorithms in computational geometry. 
For Rich Lines and Exact Fitting, we present a randomized Monte Carlo algorithm that achieves a lower running time than that of Guibas et al.’s algorithm [Computational Geometry 1996], for a wide range of the parameter λ. We derive lower-bound results showing that, for λ = Ω(√{n log n}), the upper bound on the running time of this randomized algorithm matches the lower bound that we derive on the time complexity of Rich Lines in the algebraic computation trees model.
For Line Cover, we present two kernelization algorithms: a randomized Monte Carlo algorithm and a deterministic algorithm. Both algorithms improve the running time of existing kernelization algorithms for Line Cover. We derive lower-bound results showing that the running time of the randomized algorithm we present comes close to the lower bound we derive on the time complexity of kernelization algorithms for Line Cover in the algebraic computation trees model.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • line cover
  • rich lines
  • exact fitting
  • kernelization
  • randomized algorithms
  • complexity lower bounds
  • algebraic computation trees

Metrics

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

Related Versions

References

  1. P. Afshani, E. Berglin, I. van Duijn, and J. Nielsen. Applications of incidence bounds in point covering problems. In Proc. 32nd International Symposium on Computational Geometry (SoCG 2016), Article No. 60, pages 1-15, 2016. Google Scholar
  2. P. K. Agarwal and S. Sen. Randomized algorithms for geometric optimization problems. In Handbook of Randomized Computation, pages 151-201. Kluwer Academic Press, 2001. Google Scholar
  3. J. Alman, M. Mnich, and V. V. Williams. Dynamic parameterized problems and algorithms. In Proc. 44th International Colloquium on Automata, Languages and Programming (ICALP 2017), Article No. 41, pages 1-16, 2017. Google Scholar
  4. M. Ben-Or. Lower bounds for algebraic computation trees. In Proc. 15th ACM Symposium on Theory of Computing (STOC 1983), pages 80-86, 1983. Google Scholar
  5. H. Brönnimann and M. T. Goodrich. Almost optimal set covers in finite VC-dimension. Discrete & Computational Geometry, 14:263-279, 1995. Google Scholar
  6. P. Bürgisser, M. Clausen, and M. Shokrollahi. Algebraic Complexity Theory. Springer, Berlin, 1997. Google Scholar
  7. C. Cao. Study on two optimization problems: Line cover and maximum genus embedding. PhD thesis, Texas A&M University, 2012. Google Scholar
  8. R. Chitnis, G. Cormode, H. Esfandiari, M. Hajiaghayi, and M. Monemizadeh. New streaming algorithms for parameterized maximal matching and beyond. In Proc. 27th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2015), pages 56-58, 2015. Google Scholar
  9. K. L. Clarkson. New applications of random sampling in computational geometry. Discrete & Computational Geometry, 2:195-222, 1987. Google Scholar
  10. K. L. Clarkson. Randomized geometric algorithms. In Computing in Euclidean Geometry, volume 1, pages 117-162. World Scientific, 1992. Google Scholar
  11. K. L. Clarkson. Algorithms for polytope covering and approximation. In Proc. 3rd Workshop Algorithms Data Struct, pages 246-252, 1993. Google Scholar
  12. K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. Google Scholar
  13. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  14. R. Downey and M. Fellows. Fundamentals of Parameterized Complexity. Springer, New York, 2013. Google Scholar
  15. J. Erickson. New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry, 16:389-418, 1996. Google Scholar
  16. V. Estivill-Castro, A. Heednacram, and F. Suraweera. Reduction rules deliver efficient FPT-algorithms for covering points with lines. Journal of Experimental Algorithmics, 14:1-7, 2010. Google Scholar
  17. V. Estivill-Castro, A. Heednacram, and F. Suraweera. FPT-algorithms for minimum-bends tours. International Journal of Computational Geometry & Applications, 21(2):189-213, 2011. Google Scholar
  18. J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, Berlin, 2010. Google Scholar
  19. H. Fournier and A. Vigneron. A tight lower bound for computing the diameter of a 3D convex polytope. Algorithmica, 49:245-257, 2007. Google Scholar
  20. D. A. Freedman. Statistical Model: Theory and Practice. Cambridge University Press, 2009. Google Scholar
  21. V. Froese, I. A. Kanj, A. Nichterlein, and R. Niedermeier. Finding points in general position. International Journal of Computational Geometry and Applications, 27(4):277-296, 2017. Google Scholar
  22. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics: A foundation for computer science. Addison-Wesley, Reading, MA, 1989. Google Scholar
  23. M. Grantson and C. Levcopoulos. Covering a set of points with a minimum number of lines. In Proc. 6th Italian Conference on Algorithms and Complexity (CIAC 2006), pages 6-17. Lecture Notes in Computer Science 3998, 2006. Google Scholar
  24. J. Gudmundsson, M. van Kreveld, and B. Speckmann. Efficient detection of patterns in 2D trajectories of moving points. Geoinformatica, 11(2):195-215, 2007. Google Scholar
  25. L. J. Guibas, M. H. Overmars, and J. M. Robert. The exact fitting problem in higher dimensions. Computational geometry, 6:215-230, 1996. Google Scholar
  26. M. Houle, H. Imai, K. Imai, J. Robert, and P. Yamamoto. Orthogonal weighted linear L₁ and L_∞ approximation and applications. Discrete Applied Mathematics, 43(3):217-232, 1993. Google Scholar
  27. M. Houle and T. Toussaint. Computing the width of a set. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10(5):761-765, 1988. Google Scholar
  28. D. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9:256-278, 1974. Google Scholar
  29. S. Kratsch, G. Philip, and S. Ray. Point line cover: the easy kernel is essentially tight. ACM Transactions on Algorithms, 12:3, 2016. Google Scholar
  30. V. A. Kumar, S. Arya, and H. H. Ramesh. Hardness of set cover with intersection 1. In Proc. 27th International Colloquium on Automata, Languages, and Programming (ICALP 2000), pages 624-635, 2000. Google Scholar
  31. S. Langerman and P. Morin. Covering things with things. Discrete & Computational Geometry, 33(4):717-729, 2005. Google Scholar
  32. J. Matousek. Range searching with efficient hierarchical cutting. Discrete Computational Geometry, 10:157-182, 1993. Google Scholar
  33. N. Megiddo and A. Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters, 1(5):194-197, 1982. Google Scholar
  34. M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2nd edition, 2017. Google Scholar
  35. M. Mnich. Big data algorithms beyond machine learning. Künstliche Intelligencz, 32:9-17, 2018. Google Scholar
  36. R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. Google Scholar
  37. J. Pach, R. Radoicic, G. Tardos, and G. Toth. Improving the crossing lemma by finding more crossings in sparse graphs. Discrete & Computational Geometry, 36(4):527-552, 2006. Google Scholar
  38. F. Preparata and I. Shamos. Computational Geometry: An Introduction. 2nd edn. Texts and Monographs in Computer Science. Springer, New York, 1985. Google Scholar
  39. W. Rudin. Principles of Mathematical Analysis. McGraw-Hill, 3rd edition, 1976. Google Scholar
  40. E. Szemerédi and W. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3-4):381-392, 1983. Google Scholar
  41. J. Wang, W. Li, and J. Chen. A parameterized algorithm for the hyperplane-cover problem. Theoretical Computer Science, 411:4005-4009, 2010. Google Scholar
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