Sharif Digital Repository

We study the problem of preclustering a set B of imprecise points in Rd: 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: = { b1, … , bn} be a collection of disjoint balls in Rd, where each ball bi specifies the possible locations of an input point pi. A partition C of B into subsets is called an (f(k) , α) -preclustering (with respect to the specific k-clustering variant under consideration) if (i) C consists of... 

The visibility graph of a polygon corresponds to its internal diagonals and boundary edges. For each vertex on the boundary of the polygon, we have a vertex in this graph and if two vertices of the polygon see each other there is an edge between their corresponding vertices in the graph. Two vertices of a polygon see each other if and only if their connecting line segment completely lies inside the polygon. Recognizing visibility graphs is the problem of deciding whether there is a simple polygon whose visibility graph is isomorphic to a given graph. Another important problem is to reconstruct such a polygon if there is any. These problems are well known and well-studied, but yet open... 

Generalizing Lee's inductive argument for counting the cells of higher order Voronoi tessellations in ℝ2 to ℝ3, 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 ℝ3, the number of regions in the order-k Voronoi tessellation is Nk−1 − (k/2)n + n, for 1 ≤ k ≤ n − 1, in which Nk−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. © Ranita Biswas, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian;... 

In this paper, a new approach toward the optimization of Access Point (AP) placement in cellular Visible light Communication (VLC) networks is proposed based on the projected gradient algorithm. The objective of the optimal placement problem is to maximize the average throughput of the network subject to constraints on the minimum illumination level and the minimum rate of the users. This optimization framework gives the enhanced AP deployment in case of users with static, nomadic, or completely mobile behavior. Taking the distribution of users, the receiver's field of view, reflection from walls and interference from neighboring APs into account makes the deployment problem complicated. To... 

In this study, we numerically determined the performance of a microscale separator comprising a lateral and a main channel to separate a two-phase flow. It was aimed to conduct continuous phase through the lateral channel and dispersed phase through the main channel. The continuous and dispersed phases were modeled as incompressible Newtonian fluids with the corresponding interface tracked by the phase-field model. The dynamics, including pressure fluctuations in the separator, were further examined. It was mechanistically demonstrated how the geometry of the separator modulates the phase separation. Further examined were the influences of various geometrical parameters on the performance of... 

A great deal of computational power and time is necessary for the simulation of highly heterogeneous fractured reservoirs with complicated geometry. Simulating such largescale complex reservoirs with both minimum time and maximum accuracy has consistently remained a topic of concern to reservoir simulation engineers worldwide. The currently used linear solvers in well-known commercial simulators that utilize classical methods such as Nested Factorization (NF) and Incomplete LU Factorization (ILU) as their preconditioners, all suffer from severe convergence problems in models with high heterogeneity and/or large number of non-neighbor connections. To overcome such problems, a novel Adaptive... 

A great deal of computational power and time is necessary for simulating highly heterogeneous fractured reservoirs with complex geometry; the efficiency of these computations is a major subject especially in large-scale heterogeneous and fractured reservoirs. So, simulating large scale, complex and fractured reservoirs with both minimum time and maximum accuracy is the scope of current work. The BiCG-Stabilized solver preconditioned by CPR-AAMG has been developed to achieve acceptable results of high efficiency and robustness for large heterogeneous fractured Black-Oil models. The solver's efficiency is demonstrated in an Iranian fractured field model with heterogeneity. As an observation,... 

We report the structural, spectroscopic, and computational studies of two new Re(i) tricarbonyl complexes bearing 2,3,6,7-tetraphenyl-1,4,5,8-tetraazaphenanthrene (Ph4TAP) and 4,5-diazafluoren-9-one (dafone) having a coordinated perrhenate group obtained via in situ superoxidation of Re(i) to Re(vii); intramolecular and intermolecular n → π∗ interactions are dominant and stabilize the molecular geometry and crystal packing. This journal is © The Royal Society of Chemistry  

In a multi-robot system, a number of autonomous robots would sense, communicate, and decide to move within a given domain to achieve a common goal. In the pursuit-evasion problem, a polygonal region is given and a robot called a pursuer tries to find some mobile targets called evaders. The goal of this problem is to design a motion strategy for the pursuer such that it can detect all the evaders. In this paper, we consider a new variant of the pursuit-evasion problem in which the robots (pursuers) each moves back and forth along an orthogonal line segment inside a simple orthogonal polygon P. We assume that P includes unpredictable, moving evaders that have bounded speed. We propose the... 

In this paper, we consider a new variant of covering in an orthogonal art gallery problem where each guard is a sliding k-transmitter. Such a guard can travel back and forth along an orthogonal line segment, say s, inside the polygon. A point p is covered by this guard if there exists a point q∈s such that pq‾ is a line segment normal to s, and has at most k intersections with the boundary walls of the polygon. The objective is to minimize the sum of the lengths of the sliding k-transmitters to cover the entire polygon. In other words, the goal is to find the minimum total length of trajectories on which the guards can travel to cover the entire polygon. We prove that this problem is NP-hard... 

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... 

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... 

“How many guards are required to cover an art gallery?” asked Victor Klee in 1973, initiated a deep and interesting research area in computational geometry. This problem, referred to as the Art Gallery Problem, has been considered thoroughly in the literature. A recent version of this problem, introduced by Sadhu et al. in CCCG'10, is related to the connectivity of the guards. In this version, for a given set of initial guards inside a given simple polygon, the goal is to obtain a minimum set of new guards, such that the new guards alongside the initial ones have a connected visibility graph. The visibility graph of a set of points inside a simple polygon is a graph whose vertices correspond... 

Given a set of points in the plane, the unit clustering problem asks for finding a minimum-size set of unit disks that cover the whole input set. We study the unit clustering problem in a distributed setting, where input data is partitioned among several machines. We present a (3 + ϵ)-approximation algorithm for the problem in the Euclidean plane, and a (4 + ϵ)-approximation algorithm for the problem under general Lp metric (p1). We also study the capacitated version of the problem, where each cluster has a limited capacity for covering the points. We present a distributed algorithm for the capacitated version of the problem that achieves an approximation factor of 4+" in the L2 plane, and a... 

Given a set P of n points in the plane, the all nearest neighbors problem asks for finding the closest point in P for each point in the set. The following folklore algorithm is used for the problem in practice: Pick a line in a random direction, project all points onto the line, and then search for the nearest neighbor of each point in a small vicinity of that point on the line. It is widely believed that the expected number of points needed to be checked by the algorithm in the vicinity of each point is O(pn) on average. We confirm this conjecture in affirmative by providing a careful analysis on the expected number of comparisons made by the algorithm. We also present a matching lower... 

We focus on two metric clusterings namely r-gather and (r, ?)-gather. The objective of r-gather is to minimize the radius of clustering, such that each cluster has at least r points. (r, ?)-gather is a version of r-gather with the extra condition that at most n? points can be left unclustered (outliers). MapReduce is a model used for processing big data. In each round, it distributes data to multiple servers, then simultaneously processes each server's data. We prove a lower bound 2 on the approximation factor of metric r-gather in the MapReduce model, even if an optimal algorithm for r-gather exists. Then, we give a (4+ δ)-approximation algorithm for r-gather in MapReduce which runs in O(... 

Given a set of points in the plane, the unit clustering problem asks for finding a minimum-size set of unit disks that cover the whole input set. We study the unit clustering problem in a distributed setting, where input data is partitioned among several machines. We present a (3 + ϵ)-approximation algorithm for the problem in the Euclidean plane, and a (4 + ϵ)-approximation algorithm for the problem under general Lp metric (p1). We also study the capacitated version of the problem, where each cluster has a limited capacity for covering the points. We present a distributed algorithm for the capacitated version of the problem that achieves an approximation factor of 4+" in the L2 plane, and a... 

Given a set P of n points in the plane, the all nearest neighbors problem asks for finding the closest point in P for each point in the set. The following folklore algorithm is used for the problem in practice: Pick a line in a random direction, project all points onto the line, and then search for the nearest neighbor of each point in a small vicinity of that point on the line. It is widely believed that the expected number of points needed to be checked by the algorithm in the vicinity of each point is O(pn) on average. We confirm this conjecture in affirmative by providing a careful analysis on the expected number of comparisons made by the algorithm. We also present a matching lower... 

We focus on two metric clusterings namely r-gather and (r, ?)-gather. The objective of r-gather is to minimize the radius of clustering, such that each cluster has at least r points. (r, ?)-gather is a version of r-gather with the extra condition that at most n? points can be left unclustered (outliers). MapReduce is a model used for processing big data. In each round, it distributes data to multiple servers, then simultaneously processes each server's data. We prove a lower bound 2 on the approximation factor of metric r-gather in the MapReduce model, even if an optimal algorithm for r-gather exists. Then, we give a (4+ δ)-approximation algorithm for r-gather in MapReduce which runs in O(... 

Give a triangulation of a set of points on the plane, dilation of any two points is defined as the ratio between the length of the shortest path of these points and their Euclidean distance. Minimum dilation triangulation is a triangulation in which the maximum dilation between any pair of the points is minimized. We give upper bounds on the dilation of the minimum dilation triangulation for two kinds of point sets: An upper bound of nsin⁡(π/n)/2 for a centrally symmetric convex point set containing n points, and an upper bound of 1.19098 for a set of points on the boundary of a semicircle. © 2018 Elsevier B.V