Mohammad Ali Abam

TCS Journal 2019 Journal Article

Geometric spanner games

• Mohammad Ali Abam
• Mahnaz Sadat Qafari

Consider a scenario in which several agents are located in the Euclidean space, and the agents want to create a network in which everyone has fast access to all or some other agents. Geometric t-spanners are examples of such a network providing fast connections between the nodes of the network for some fixed value t, i. e. the length of the shortest path between any two nodes in the network is at most t times their Euclidean distance. Geometric t-spanners have been extensively studied in the area of computational geometry where they are created by a central authority. In this paper, we investigate a situation in which selfish agents want to create such a network in the absence of a central authority. To this end, we introduce two different non-cooperative games: the t-spanner game and the sink t-spanner game, where it is vital for the agents to have a fast connection to all other agents or to a special node, respectively. We study the existence of the Nash equilibrium in both games and present some structural properties of the resulting networks in the Nash equilibrium.

TCS Journal 2019 Journal Article

Visibility testing and counting for uncertain segments

• Mohammad Ali Abam
• Sharareh Alipour
• Mohammad Ghodsi
• Mohammad Mahdian

We study two well-known planar visibility problems, namely visibility testing and visibility counting, in a model where there is uncertainty about the input data. The standard versions of these problems are defined as follows: we are given a set S of n segments in R 2, and we would like to preprocess S so that we can quickly answer queries of the form: is the given query segment s ∈ S visible from the given query point q ∈ R 2 (for visibility testing) and how many segments in S are visible from the given query point q ∈ R 2 (for visibility counting). In our model of uncertainty, each segment may or may not exist, and if it does, it is located in one of finitely many possible locations, given by a discrete probability distribution. In this setting, the probabilistic visibility testing problem (PVTP, for short) is to compute the probability that a given segment s ∈ S is visible from a given query point q and the probabilistic visibility counting problem (PVCP, for short) is to compute the expected number of segments in S that are visible from a query point q. We first show that PVTP is #P-complete. In the special case where uncertainty is only about whether segments exist and not about their location, we show that PVTP is solvable in O ( n log ⁡ n ) time. Our algorithm for PVTP combined with linearity of expectation gives an O ( n 2 log ⁡ n ) time algorithm for PVCP. Using the algorithm for PVTP, together with a few old tricks, we can show that one can preprocess S in O ( n 5 log ⁡ n ) time into a data structure of size O ( n 4 ), so that each PVTP query for a fixed segment s can be answered in O ( log ⁡ n ) time. We also give a faster 2-approximation algorithm for this problem. At the end, we improve the approximation factor of the algorithm.

SODA Conference 2017 Conference Paper

Geodesic Spanners for Points on a Polyhedral Terrain

• Mohammad Ali Abam
• Mark de Berg
• Mohammad Javad Rezaei Seraji

Let S be a set S of n points on a polyhedral terrain T in ℝ 3, and let ∊ > 0 be a fixed constant. We prove that S admits a (2 + ∊)-spanner with O ( n log n ) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in ℝ d admits an additively weighted (2 + ∊)-spanner with O ( n ) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ∊), and almost matches the lower bound.

TCS Journal 2016 Journal Article

Efficiently approximating color-spanning balls

• Payam Khanteimouri
• Ali Mohades
• Mohammad Ali Abam
• Mohammad Reza Kazemi

Suppose n colored points with k colors in R d are given. The Smallest Color-Spanning Ball (SCSB) is the smallest ball containing at least one point of each color. As the computation of the SCSB in L p metric ( p ≥ 1 ) is time-consuming, we focus on approximately computing the SCSB in near-linear time. Initially, we propose a 3-approximation algorithm running in O ( n log ⁡ n ) time. This algorithm is then utilized to present a ( 1 + ε ) -approximation algorithm with the running time of O ( ( 1 ε ) d n log ⁡ n ). We improve the running time to O ( ( 1 ε ) d n ) using randomized techniques. Afterward, spanning colors with two balls is studied. For a special case where d = 1, there is an algorithm with O ( n 2 ) time. We demonstrate that for any ε > 0 under the assumption that SETH is true, no approximation algorithm running in O ( n 2 − ε ) time exists for the problem even in one-dimensional space. Nevertheless, we consider the L ∞ metric where a ball is an axis-parallel hypercube and present a ( 1 + ε ) -approximation algorithm running in O ( ( 1 ε ) 2 d ( n 2 k ) log 2 ⁡ n ) time which is remarkable when k is large. This time can be reduced to O ( ( 1 ε ) n 2 k log ⁡ n ) when d = 1.

SODA Conference 2007 Conference Paper

Region-fault tolerant geometric spanners

• Mohammad Ali Abam
• Mark de Berg
• Mohammad Farshi
• Joachim Gudmundsson