Reprint of: Theta-3 is connected Aichholzer, Oswin; Bae, Sang Won; Barba, Luis ...
Computational geometry : theory and applications,
July 2015, Letnik:
48, Številka:
5
Journal Article
Recenzirano
Odprti dostop
In this paper, we show that the θ-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.
Theta-3 is connected Aichholzer, Oswin; Bae, Sang Won; Barba, Luis ...
Computational geometry : theory and applications,
10/2014, Letnik:
47, Številka:
9
Journal Article
Recenzirano
Odprti dostop
In this paper, we show that the θ-graph with three cones is connected. We also provide an alternative proof of the connectivity of the Yao graph with three cones.
We show that, for any constant
, there exists an integer constant
such that the Yao–Yao graph with parameter
defined on a civilized unit disk graph is a geometric spanner of stretch factor
. This ...improves the results of Wang and Li in several aspects, as described in the paper. This partially answers an open problem posed by Demaine, Mitchell and O’Rourke about the spanner properties of Yao–Yao graphs. We also show that the Yao–Yao graph with parameter
defined on the complete Euclidean graph is not plane.
We study a fault tolerant differential evolution based topology control mechanism, called TCM-Y, to direct the movements of autonomous vehicles that dynamically adjust their speed and directions in ...MANETs. TCM-Y uses a Yao graph inspired fitness function to preserve a node's minimum desired number of connections with its neighbors while uniformly dispersing mobile nodes in an unknown terrain. We present a formal analysis of TCM-Y to show that it provides a fault tolerant node spreading mechanism since any node will have at least k neighbors at all times. The effectiveness of TCM-Y is evaluated by comparing it with a popular deterministic node spreading mechanism called Constrained Coverage for Mobile Sensor Nodes (CC-MSN) that has similar objectives as TCM-Y. Experimental results obtained from our simulation software show that TCM-Y performs significantly better than CC-MSN with respect to normalized area coverage, average distance traveled, average connectivity, and the minimum connectivity achieved by mobile nodes.
We present a local distributed algorithm that, given a wireless ad hoc network modeled as a unit disk graph U in the plane, constructs a planar power spanner of U whose degree is bounded by k and ...whose stretch factor is bounded by 1 + (2sin pi/k) p , where k ges 10 is an integer parameter and p isin 2, 5 is the power exponent constant. For the same degree bound k, the stretch factor of our algorithm significantly improves the previous best bounds by Song et al. We show that this bound is near-optimal by proving that the slightly smaller stretch factor of 1 + (2sin pi/k+1) p is unattainable for the same degree bound k. In contrast to previous algorithms for the problem, the presented algorithm is local. As a consequence, the algorithm is highly scalable and robust. Finally, while the algorithm is efficient and easy to implement in practice, it relies on deep insights on the geometry of unit disk graphs and novel techniques that are of independent interest.
Wireless ad hoc network nodes suffer from limited energy supply. To reduce the power consumption of the routing protocols, many routing algorithms use a subset of the nodes to participate in the ...routing task. For that reason, topology control for wireless ad hoc networks got great attention in recent years. Geographical locations of the network nodes are used in many topology control algorithms to enhance performance and reduce overhead. In this paper, we review the most known geographical-based topology control algorithms for Ad Hoc Networks with a focus on connectivity, locality, planarity, stretch factor, node degree, and scalability. We conduct a comparison between these algorithms as well.
The advent of wireless communication and networking in the last two decades has led to the need of modification in the regular graphs used as spanners. The spanner is a sub graph of the original ...graph which connects the essential nodes for transmission of the message. For this purpose the Omni directional antennas are usually used and the “spanner-graph” performance metric is a constant multiplied by the same of the original graph. This constant is known as the “stretch factor”. One of the most common attribute for wireless communication is the energy required for faithful transmission of a message between two nodes. But the Omni directional antennas lead to interference and wastage of bandwidth and energy. The nodes of wireless communication are however neither always static nor equipped with any infrastructure. Rather the same might as well be ad-hoc and mobile. Another well used notion is that of the unit disk graph (UDG), where a node can communicate only if the other nodes are within the disk of unit radius. However the graph being dynamic in nature, the nodes do not have fixed transmission radii and the same changes according to the power requirement of transmission. This work of ours mainly deals with the different graphs being used as spanners. It explains a few algorithms described in other papers which it reviewed. The associated algorithms are related to Yao graph. This graph and its modifications are discussed and it is explained how they could be used energy efficiently. The Yao-Yao graph for example can be used as a spanner for certain specific values of stretch factors.
Let D be a set of n pairwise disjoint disks in the plane. Consider the metric space in which the distance between any two disks D and D′ in D is the length of the shortest line segment that connects ...D and D′. For any real number ε>0, we show how to obtain a (1+ε)-spanner for this metric space that has at most (2π/ε)⋅n edges. The previously best known result is by Bose et al. (2011) 1. Their (1+ε)-spanner is a variant of the Yao graph and has at most (8π/ε)⋅n edges. Our new spanner is also a variant of the Yao graph.
Closest-pair queries in fat rectangles Bae, Sang Won; Smid, Michiel
Computational geometry : theory and applications,
October 2019, 2019-10-00, Letnik:
83
Journal Article
Recenzirano
Odprti dostop
In the range closest pair problem, we want to construct a data structure storing a set S of n points in the plane, such that for any axes-parallel query rectangle R, the closest pair in the set R∩S ...can be reported. The currently best result for this problem is by Xue et al. (SoCG 2018). Their data structure has size O(nlog2n) and query time O(log2n). We show that a data structure of size O(nlogn) can be constructed in O(nlogn) time, such that queries can be answered in O(logn+flogf) time, where f is the aspect ratio of R. Thus, for fat query rectangles, the query time is O(logn). This result is obtained by reducing the range closest pair problem to standard range searching problems on the points of S.
PDF
