3 Search Results for "Saghafian, Morteza"

Document
DOI: 10.4230/LIPIcs.SoCG.2021.16
Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory

Authors: Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Generalizing Lee’s inductive argument for counting the cells of higher order Voronoi tessellations in ℝ² to ℝ³, we get precise relations in terms of Morse theoretic quantities for piecewise constant functions on planar arrangements. Specifically, we prove that for a generic set of n ≥ 5 points in ℝ³, the number of regions in the order-k Voronoi tessellation is N_{k-1} - binom(k,2)n + n, for 1 ≤ k ≤ n-1, in which N_{k-1} is the sum of Euler characteristics of these function’s first k-1 sublevel sets. We get similar expressions for the vertices, edges, and polygons of the order-k Voronoi tessellation.
Cite as

Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. Counting Cells of Order-k Voronoi Tessellations in ℝ³ with Morse Theory. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{biswas_et_al:LIPIcs.SoCG.2021.16,
  author =	{Biswas, Ranita and Cultrera di Montesano, Sebastiano and Edelsbrunner, Herbert and Saghafian, Morteza},
  title =	{{Counting Cells of Order-k Voronoi Tessellations in \mathbb{R}³ with Morse Theory}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.16},
  URN =		{urn:nbn:de:0030-drops-138152},
  doi =		{10.4230/LIPIcs.SoCG.2021.16},
  annote =	{Keywords: Voronoi tessellations, Delaunay mosaics, arrangements, convex polytopes, Morse theory, counting}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.32
The Density Fingerprint of a Periodic Point Set

Authors: Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
Modeling a crystal as a periodic point set, we present a fingerprint consisting of density functions that facilitates the efficient search for new materials and material properties. We prove invariance under isometries, continuity, and completeness in the generic case, which are necessary features for the reliable comparison of crystals. The proof of continuity integrates methods from discrete geometry and lattice theory, while the proof of generic completeness combines techniques from geometry with analysis. The fingerprint has a fast algorithm based on Brillouin zones and related inclusion-exclusion formulae. We have implemented the algorithm and describe its application to crystal structure prediction.
Cite as

Herbert Edelsbrunner, Teresa Heiss, Vitaliy Kurlin, Philip Smith, and Mathijs Wintraecken. The Density Fingerprint of a Periodic Point Set. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{edelsbrunner_et_al:LIPIcs.SoCG.2021.32,
  author =	{Edelsbrunner, Herbert and Heiss, Teresa and Kurlin, Vitaliy and Smith, Philip and Wintraecken, Mathijs},
  title =	{{The Density Fingerprint of a Periodic Point Set}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.32},
  URN =		{urn:nbn:de:0030-drops-138310},
  doi =		{10.4230/LIPIcs.SoCG.2021.32},
  annote =	{Keywords: Lattices, periodic sets, isometries, Dirichlet-Voronoi domains, Brillouin zones, bottleneck distance, stability, continuity, crystal database}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.3
Preclustering Algorithms for Imprecise Points

Authors: Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, and Morteza Saghafian

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the problem of preclustering a set B of imprecise points in ℝ^d: we wish to cluster the regions specifying the potential locations of the points such that, no matter where the points are located within their regions, the resulting clustering approximates the optimal clustering for those locations. We consider k-center, k-median, and k-means clustering, and obtain the following results. Let B:={b₁,…,b_n} be a collection of disjoint balls in ℝ^d, where each ball b_i specifies the possible locations of an input point p_i. A partition 𝒞 of B into subsets is called an (f(k),α)-preclustering (with respect to the specific k-clustering variant under consideration) if (i) 𝒞 consists of f(k) preclusters, and (ii) for any realization P of the points p_i inside their respective balls, the cost of the clustering on P induced by 𝒞 is at most α times the cost of an optimal k-clustering on P. We call f(k) the size of the preclustering and we call α its approximation ratio. We prove that, even in ℝ^1, one may need at least 3k-3 preclusters to obtain a bounded approximation ratio - this holds for the k-center, the k-median, and the k-means problem - and we present a (3k,1) preclustering for the k-center problem in ℝ^1. We also present various preclusterings for balls in ℝ^d with d⩾2, including a (3k,α)-preclustering with α≈13.9 for the k-center and the k-median problem, and α≈254.7 for the k-means problem.
Cite as

Mohammad Ali Abam, Mark de Berg, Sina Farahzad, Mir Omid Haji Mirsadeghi, and Morteza Saghafian. Preclustering Algorithms for Imprecise Points. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abam_et_al:LIPIcs.SWAT.2020.3,
  author =	{Abam, Mohammad Ali and de Berg, Mark and Farahzad, Sina and Mirsadeghi, Mir Omid Haji and Saghafian, Morteza},
  title =	{{Preclustering Algorithms for Imprecise Points}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{3:1--3:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.3},
  URN =		{urn:nbn:de:0030-drops-122503},
  doi =		{10.4230/LIPIcs.SWAT.2020.3},
  annote =	{Keywords: Geometric clustering, k-center, k-means, k-median, imprecise points, approximation algorithms}
}
  • Refine by Author
  • 2 Edelsbrunner, Herbert
  • 2 Saghafian, Morteza
  • 1 Abam, Mohammad Ali
  • 1 Biswas, Ranita
  • 1 Cultrera di Montesano, Sebastiano
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Brillouin zones
  • 1 Delaunay mosaics
  • 1 Dirichlet-Voronoi domains
  • 1 Geometric clustering
  • 1 Lattices
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2021
  • 1 2020

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 Imprint Privacy Contact