Search Results

Documents authored by Mehr, Mehran

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.37
On One-Round Discrete Voronoi Games

Authors: Mark de Berg, Sándor Kisfaludi-Bak, and Mehran Mehr

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Let V be a multiset of n points in R^d, which we call voters, and let k >=slant 1 and l >=slant 1 be two given constants. We consider the following game, where two players P and Q compete over the voters in V: First, player P selects a set P of k points in R^d, and then player Q selects a set Q of l points in R^d. Player P wins a voter v in V iff dist(v,P) <=slant dist(v,Q), where dist(v,P) := min_{p in P} dist(v,p) and dist(v,Q) is defined similarly. Player P wins the game if he wins at least half the voters. The algorithmic problem we study is the following: given V, k, and l, how efficiently can we decide if player P has a winning strategy, that is, if P can select his k points such that he wins the game no matter where Q places her points. Banik et al. devised a singly-exponential algorithm for the game in R^1, for the case k=l. We improve their result by presenting the first polynomial-time algorithm for the game in R^1. Our algorithm can handle arbitrary values of k and l. We also show that if d >= 2, deciding if player P has a winning strategy is Sigma_2^P-hard when k and l are part of the input. Finally, we prove that for any dimension d, the problem is contained in the complexity class exists for all R, and we give an algorithm that works in polynomial time for fixed k and l.
Cite as

Mark de Berg, Sándor Kisfaludi-Bak, and Mehran Mehr. On One-Round Discrete Voronoi Games. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2019.37,
  author =	{de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Mehr, Mehran},
  title =	{{On One-Round Discrete Voronoi Games}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.37},
  URN =		{urn:nbn:de:0030-drops-115339},
  doi =		{10.4230/LIPIcs.ISAAC.2019.37},
  annote =	{Keywords: competitive facility location, plurality point}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.4
Minimum Perimeter-Sum Partitions in the Plane

Authors: Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) is minimized, where CH(P_i) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n^2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time.
Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Minimum Perimeter-Sum Partitions in the Plane. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.4,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Minimum Perimeter-Sum Partitions in the Plane}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.4},
  URN =		{urn:nbn:de:0030-drops-72048},
  doi =		{10.4230/LIPIcs.SoCG.2017.4},
  annote =	{Keywords: Computational geometry, clustering, minimum-perimeter partition, convex hull}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.5
Range-Clustering Queries

Authors: Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In a geometric k-clustering problem the goal is to partition a set of points in R^d into k subsets such that a certain cost function of the clustering is minimized. We present data structures for orthogonal range-clustering queries on a point set S: given a query box Q and an integer k > 2, compute an optimal k-clustering for the subset of S inside Q. We obtain the following results. * We present a general method to compute a (1+epsilon)-approximation to a range-clustering query, where epsilon>0 is a parameter that can be specified as part of the query. Our method applies to a large class of clustering problems, including k-center clustering in any Lp-metric and a variant of k-center clustering where the goal is to minimize the sum (instead of maximum) of the cluster sizes. * We extend our method to deal with capacitated k-clustering problems, where each of the clusters should not contain more than a given number of points. * For the special cases of rectilinear k-center clustering in R^1, and in R^2 for k = 2 or 3, we present data structures that answer range-clustering queries exactly.
Cite as

Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2017.5,
  author =	{Abrahamsen, Mikkel and de Berg, Mark and Buchin, Kevin and Mehr, Mehran and Mehrabi, Ali D.},
  title =	{{Range-Clustering Queries}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.5},
  URN =		{urn:nbn:de:0030-drops-72147},
  doi =		{10.4230/LIPIcs.SoCG.2017.5},
  annote =	{Keywords: Geometric data structures, clustering, k-center problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.32
Faster Algorithms for Computing Plurality Points

Authors: Mark de Berg, Joachim Gudmundsson, and Mehran Mehr

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector <w_1(v), ...,w_d(v)> and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).
Cite as

Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster Algorithms for Computing Plurality Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.SoCG.2016.32,
  author =	{de Berg, Mark and Gudmundsson, Joachim and Mehr, Mehran},
  title =	{{Faster Algorithms for Computing Plurality Points}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.32},
  URN =		{urn:nbn:de:0030-drops-59248},
  doi =		{10.4230/LIPIcs.SoCG.2016.32},
  annote =	{Keywords: computational geometry, computational social choice, voting theory, plurality points, Condorcet points}
}
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