3 Search Results for "Abam, Mohammad"

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}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.186
Geometric Spanners for Points Inside a Polygonal Domain

Authors: Mohammad Ali Abam, Marjan Adeli, Hamid Homapour, and Pooya Zafar Asadollahpoor

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Let P be a set of n points inside a polygonal domain D. A polygonal domain with h holes (or obstacles) consists of h disjoint polygonal obstacles surrounded by a simple polygon which itself acts as an obstacle. We first study t-spanners for the set P with respect to the geodesic distance function d where for any two points p and q, d(p,q) is equal to the Euclidean length of the shortest path from p to q that avoids the obstacles interiors. For a case where the polygonal domain is a simple polygon (i.e., h=0), we construct a (sqrt(10)+eps)-spanner that has O(n log^2 n) edges where eps is the a given positive real number. For a case where there are h holes, our construction gives a (5+eps)-spanner with the size of O(sqrt(h) n log^2 n). Moreover, we study t-spanners for the visibility graph of P (VG(P), for short) with respect to a hole-free polygonal domain D. The graph VG(P) is not necessarily a complete graph or even connected. In this case, we propose an algorithm that constructs a (3+eps)-spanner of size almost O(n^{4/3}). In addition, we show that there is a set P of n points such that any (3-eps)-spanner of VG(P) must contain almost n^2 edges.
Cite as

Mohammad Ali Abam, Marjan Adeli, Hamid Homapour, and Pooya Zafar Asadollahpoor. Geometric Spanners for Points Inside a Polygonal Domain. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 186-197, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{abam_et_al:LIPIcs.SOCG.2015.186,
  author =	{Abam, Mohammad Ali and Adeli, Marjan and Homapour, Hamid and Asadollahpoor, Pooya Zafar},
  title =	{{Geometric Spanners for Points Inside a Polygonal Domain}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{186--197},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.186},
  URN =		{urn:nbn:de:0030-drops-51378},
  doi =		{10.4230/LIPIcs.SOCG.2015.186},
  annote =	{Keywords: Geometric Spanners, Polygonal Domain, Visibility Graph}
}
Document
DOI: 10.4230/DagSemProc.08081.2
Kinetic kd-Trees and Longest-Side kd-Trees

Authors: Mohammad Abam, Mark de Berg, and Bettina Speckmann

Published in: Dagstuhl Seminar Proceedings, Volume 8081, Data Structures (2008)

Abstract
We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in~$Reals^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search que-ries in~$O(n^{1-1/d}+k)$ time, where~$k$ is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes~$O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in~$O(log n)$ time, and each point is involved in~$O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in~$Reals^2$. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in~$O((1/epsilon)log^2 n)$ time. The KDS processes~$O(n^3log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in~$O(log^2 n)$ time, and each point is involved in~$O(log n)$ certificates.
Cite as

Mohammad Abam, Mark de Berg, and Bettina Speckmann. Kinetic kd-Trees and Longest-Side kd-Trees. In Data Structures. Dagstuhl Seminar Proceedings, Volume 8081, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{abam_et_al:DagSemProc.08081.2,
  author =	{Abam, Mohammad and de Berg, Mark and Speckmann, Bettina},
  title =	{{Kinetic kd-Trees and Longest-Side kd-Trees}},
  booktitle =	{Data Structures},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08081.2},
  URN =		{urn:nbn:de:0030-drops-15307},
  doi =		{10.4230/DagSemProc.08081.2},
  annote =	{Keywords: Kinetic data structures, kd-tree, longest-side kd-tree}
}
  • Refine by Author
  • 2 Abam, Mohammad Ali
  • 2 de Berg, Mark
  • 1 Abam, Mohammad
  • 1 Adeli, Marjan
  • 1 Asadollahpoor, Pooya Zafar
  • Show More...

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

  • Refine by Keyword
  • 1 Geometric Spanners
  • 1 Geometric clustering
  • 1 Kinetic data structures
  • 1 Polygonal Domain
  • 1 Visibility Graph
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2008
  • 1 2015
  • 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