LIPIcs.SoCG.2023.4.pdf
- Filesize: 1.1 MB
- 15 pages
Document
Computing Instance-Optimal Kernels in Two Dimensions
Authors
Pankaj K. Agarwal 
,
Sariel Har-Peled
-
Part of:
Volume:
39th International Symposium on Computational Geometry (SoCG 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-06-09
File
Document Identifiers
Author Details
Cite As Get BibTex
Pankaj K. Agarwal and Sariel Har-Peled. Computing Instance-Optimal Kernels in Two Dimensions. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.4
Abstract
Let P be a set of n points in ℝ². For a parameter ε ∈ (0,1), a subset C ⊆ P is an ε-kernel of P if the projection of the convex hull of C approximates that of P within (1-ε)-factor in every direction. The set C is a weak ε-kernel of P if its directional width approximates that of P in every direction. Let 𝗄_ε(P) (resp. 𝗄^𝗐_ε(P)) denote the minimum-size of an ε-kernel (resp. weak ε-kernel) of P. We present an O(n 𝗄_ε(P)log n)-time algorithm for computing an ε-kernel of P of size 𝗄_ε(P), and an O(n²log n)-time algorithm for computing a weak ε-kernel of P of size 𝗄^𝗐_ε(P). We also present a fast algorithm for the Hausdorff variant of this problem. In addition, we introduce the notion of ε-core, a convex polygon lying inside ch(P), prove that it is a good approximation of the optimal ε-kernel, present an efficient algorithm for computing it, and use it to compute an ε-kernel of small size.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- Coreset
- approximation
- kernel
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Pankaj K. Agarwal and Sariel Har-Peled. Computing optimal kernels in two dimensions. CoRR, abs/2207.07211, 2022. URL: https://doi.org/10.48550/arXiv.2207.07211.
- Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. Assoc. Comput. Mach., 51(4):606-635, 2004. URL: https://doi.org/10.1145/1008731.1008736.
- Pankaj K. Agarwal, Sariel Har-Peled, and Hai Yu. Robust shape fitting via peeling and grating coresets. Discret. Comput. Geom., 39(1-3):38-58, 2008. URL: https://doi.org/10.1007/s00454-007-9013-2.
- Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. Efficient algorithms for k-regret minimizing sets. In Costas S. Iliopoulos, Solon P. Pissis, Simon J. Puglisi, and Rajeev Raman, editors, 16th Int. Symp. Exper. Alg., (SEA), pages 7:1-7:23, 2017. URL: https://doi.org/10.4230/LIPIcs.SEA.2017.7.
- Pankaj K. Agarwal and Hai Yu. A space-optimal data-stream algorithm for coresets in the plane. In Jeff Erickson, editor, Proc. 23rd Annu. Sympos. Comput. Geom. (SoCG), pages 1-10. ACM, 2007. URL: https://doi.org/10.1145/1247069.1247071.
- Avrim Blum, Sariel Har-Peled, and Benjamin Raichel. Sparse approximation via generating point sets. ACM Trans. Algo., 15(3):32:1-32:16, 2019. URL: https://doi.org/10.1145/3302249.
- Hervé Brönnimann and Michael T. Goodrich. Almost optimal set covers in finite vc-dimension. Discrete Comput. Geom., 14(4):463-479, 1995. URL: https://doi.org/10.1007/BF02570718.
- Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. k-regret minimizing set: Efficient algorithms and hardness. In 20th Int. Conf. Data. Theory, (ICDT), pages 11:1-11:19, 2017. URL: https://doi.org/10.4230/LIPIcs.ICDT.2017.11.
- Timothy M. Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. Theory Appl., 35(1-2):20-35, 2006. URL: https://doi.org/10.1016/j.comgeo.2005.10.002.
- Bernard Chazelle and Leonidas J. Guibas. Visibility and intersection problems in plane geometry. Discret. Comput. Geom., 4:551-581, 1989. URL: https://doi.org/10.1007/BF02187747.
- Kenneth L. Clarkson. Algorithms for polytope covering and approximation. In Frank K. H. A. Dehne, Jörg-Rüdiger Sack, Nicola Santoro, and Sue Whitesides, editors, Proc. 3th Workshop Algorithms Data Struct. (WADS), volume 709 of Lect. Notes in Comp. Sci., pages 246-252. Springer, 1993. URL: https://doi.org/10.1007/3-540-57155-8_252.
- Gautam Das and Michael T. Goodrich. On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees. Comput. Geom., 8:123-137, 1997. URL: https://doi.org/10.1016/S0925-7721(97)00006-0.
- Subir Kumar Ghosh and Anil Maheshwari. An optimal algorithm for computing a minimum nested nonconvex polygon. Information Processing Letters, 36(6):277-280, 1990. URL: https://doi.org/10.1016/0020-0190(90)90038-Y.
- Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, and Jack Snoeyink. Approximating polygons and subdivisions with minimum-link paths. Int. J. Comput. Geom. Appl., 3(04):383-415, 1993. URL: https://doi.org/10.1142/S0218195993000257.
- John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms, 18(3):403-431, 1995. URL: https://doi.org/10.1006/jagm.1995.1017.
- Georgiy Klimenko and Benjamin Raichel. Fast and exact convex hull simplification. In Mikolaj Bojanczyk and Chandra Chekuri, editors, Proc. 41th Conf. Found. Soft. Tech. Theoret. Comput. Sci. (FSTTCS), volume 213 of LIPIcs, pages 26:1-26:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2021.26.
- C. C. Lee and D. T. Lee. On a circle-cover minimization problem. Inf. Process. Lett., 18(2):109-115, 1984. URL: https://doi.org/10.1016/0020-0190(84)90033-4.
- Joseph SB Mitchell and Valentin Polishchuk. Minimum-perimeter enclosures. Information Processing Letters, 107(3-4):120-124, 2008. URL: https://doi.org/10.1016/j.ipl.2008.02.007.
- Joseph SB Mitchell and Subhash Suri. Separation and approximation of polyhedral objects. Comput. Geom. Theory Appl., 5(2):95-114, 1995. URL: https://doi.org/10.1016/0925-7721(95)00006-U.
- Cao An Wang. Finding minimal nested polygons. BIT Numerical Mathematics, 31(2):230-236, 1991. URL: https://doi.org/10.1007/bf01931283.
- Cao An Wang and Edward P. F. Chan. Finding the minimum visible vertex distance between two non-intersecting simple polygons. In Alok Aggarwal, editor, Proc. 2nd Annu. Sympos. Comput. Geom. (SoCG), pages 34-42. ACM, 1986. URL: https://doi.org/10.1145/10515.10519.
- Yanhao Wang, Michael Mathioudakis, Yuchen Li, and Kian-Lee Tan. Minimum coresets for maxima representation of multidimensional data. In Leonid Libkin, Reinhard Pichler, and Paolo Guagliardo, editors, Proc. 40th Symp. Principles Database Sys. PODS, pages 138-152. ACM, 2021. URL: https://doi.org/10.1145/3452021.3458322.
- Hai Yu, Pankaj K. Agarwal, Raghunath Poreddy, and Kasturi R. Varadarajan. Practical methods for shape fitting and kinetic data structures using coresets. Algorithmica, 52(3):378-402, 2008. URL: https://doi.org/10.1007/s00453-007-9067-9.