LIPIcs.SoCG.2023.64.pdf
- Filesize: 1.05 MB
- 5 pages
Document
Greedy Permutations and Finite Voronoi Diagrams (Media Exposition)
Authors
Oliver A. Chubet 
,
Donald R. Sheehy ,
-
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
Oliver A. Chubet, Paul Macnichol, Parth Parikh, Donald R. Sheehy, and Siddharth S. Sheth. Greedy Permutations and Finite Voronoi Diagrams (Media Exposition). In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.SoCG.2023.64
Abstract
We illustrate the computation of a greedy permutation using finite Voronoi diagrams. We describe the neighbor graph, which is a sparse graph data structure that facilitates efficient point location to insert a new Voronoi cell. This data structure is not dependent on a Euclidean metric space. The greedy permutation is computed in O(nlog Δ) time for low-dimensional data using this method [Sariel Har-Peled and Manor Mendel, 2006; Donald R. Sheehy, 2020].
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
Keywords
- greedy permutation
- Voronoi diagrams
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Kenneth L. Clarkson. Nearest neighbor queries in metric spaces. Discrete & Computational Geometry, 22(1):63-93, 1999.
- M.E Dyer and A.M Frieze. A simple heuristic for the p-centre problem. Operations Research Letters, 3(6):285-288, 1985. URL: https://doi.org/10.1016/0167-6377(85)90002-1.
- Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. URL: https://doi.org/10.1016/0304-3975(85)90224-5.
-
Sariel Har-Peled and Manor Mendel. Fast construction of nets in low dimensional metrics, and their applications. SIAM Journal on Computing, 35(5):1148-1184, 2006.
-
Daniel J Rosenkrantz, Richard E Stearns, and Philip M Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563-581, 1977.
-
Donald R. Sheehy. greedypermutations. https://anonymous.4open.science/r/greedypermutation-C50B, 2020.