The problem of computing the exact stretch factor (i.e., the tight bound on the worst case stretch factor) of a Delaunay triangulation is one of the longstanding open problems in computational geometry. Over the years, a series of upper and lower bounds on the exact stretch factor have been obtained but the gap between them is still large. An alternative approach to solving the problem is to develop techniques for computing the exact stretch factor of "easier" types of Delaunay triangulations, in particular those defined using regular-polygons instead of a circle. Tight bounds exist for Delaunay triangulations defined using an equilateral triangle and a square. In this paper, we determine the exact stretch factor of Delaunay triangulations defined using a regular hexagon: It is 2. We think that the main contribution of this paper are the two techniques we have developed to compute tight upper bounds for the stretch factor of Hexagon-Delaunay triangulations.

Let ${\cal P}$ be a set of $n$ points embedded in the plane, and let ${\cal C}$ be the complete Euclidean graph whose point-set is ${\cal P}$. Each edge in ${\cal C}$ between two points $p, q$ is realized as the line segment $[pq]$, and is assigned a weight equal to the Euclidean distance $|pq|$. In this paper, we show how to construct in $O(n\lg{n})$ time a plane spanner of ${\cal C}$ of maximum degree at most 4 and stretch factor at most 20. This improves a long sequence of results on the construction of plane spanners of ${\cal C}$. Our result matches the smallest known upper bound of 4 by Bonichon et al. on the maximum degree of plane spanners of ${\cal C}$, while significantly improving their stretch factor upper bound from 156.82 to 20. The construction of our spanner is based on Delaunay triangulations defined with respect to the equilateral-triangle distance, and uses a different approach than that used by Bonichon et al. Our approach leads to a simple and intuitive construction of a well-structured spanner, and reveals useful structural properties of the Delaunay triangulations defined with respect to the equilateral-triangle distance. The structure of the constructed spanner implies that when ${\cal P}$ is in convex position, the maximum degree of this spanner is at most 3. Combining the above degree upper bound with the fact that 3 is a lower bound on the maximum degree of any plane spanner of ${\cal C}$ when the point-set ${\cal P}$ is in convex position, the results in this paper give a tight bound of 3 on the maximum degree of plane spanners of ${\cal C}$ for point-sets in convex position.

Let ϵ be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t ≥ 1, a spanning subgraph G of ϵ is said to be a t-spanner, or simply a spanner, if for any pair of vertices u, v in ϵ the distance between u and v in G is at most t times their distance in ϵ. A spanner is plane if its edges do not cross.

We study student understanding of the use of a tree structure in the context of an introductory web development course. In particular, we analyze student answers as they use a tree structure to construct file references in web pages. More fundamentally, our study initiates a bottom-up study of computational thinking by identifying the computational thinking mistakes that students make when they are learning resource referencing for web development. Our preliminary results suggest that students do not necessarily learn abstract concepts (like trees) and abstract rules of reasoning (composing relative and absolute tree paths) by just working with folders and composing file references alone.

We describe a framework for implementing computational thinking in a broad variety of general education courses. The framework is designed to be used by faculty without formal training in information technology in order to understand and integrate computational thinking into their own general education courses. The framework includes examples of computational thinking in a variety of general education courses, as well as sample in-class activities, assignments, and other assessments for the courses. The examples in the different courses are related and differentiated using categories taken from Denning Great Principles of Computing, so that similar types of computational thinking appearing in different contexts are brought together. This aids understanding of the computational thinking found in the courses and provides a template for future work on new course materials. Specific examples of computational thinking in the design category are provided in the context of three distinct courses.

We consider the problem of computing spanners of Euclidean and unit disk graphs embedded in the two-dimensional Euclidean plane. We are particularly interested in spanners that possess useful properties such as planarity, bounded degree, and/or light weight. Such spanners have been extensively studied in the area of computational geometry and have been used as the building block for constructing efficient and reliable wireless network communication topologies. We study the above problem under two computational models: the centralized and the distributed model. In the distributed model we focus on algorithms that are local. Such algorithms are suitable for the relevant applications (e.g., wireless computing). Under the centralized model, we present an $O(n\lg n)$ time algorithm that computes a bounded-degree plane spanner of a complete Euclidean graph, where n is the number of points in the graph. Both upper bounds on the degree and the stretch factor significantly improve the previous bounds. We extend this algorithm to compute a bounded-degree plane lightweight spanner of a complete Euclidean graph. Under the distributed model, we give the first local algorithm for computing a spanner of a unit disk graph that is of bounded degree and plane. The upper bounds on the degree, stretch factor, and the locality of the algorithm dramatically improve the previous results, as shown in the paper. This algorithm can also be extended to compute a bounded-degree plane lightweight spanner of a unit disk graph. Our algorithms rely on structural and geometric results that we develop in this paper.

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 + (2\sin{\frac{\pi}{k}})^{p}, where k \geq 10 is an integer parameter and p \in [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 + (2\sin{\frac{\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.

We consider the problem of constructing bounded-degree planar geometric spanners of Euclidean and unit-disk graphs. It is well known that the Delaunay subgraph is a planar geometric spanner with stretch factor $C_{delapprox 2.42$; however, its degree may not be bounded. Our first result is a very simple linear time algorithm for constructing a subgraph of the Delaunay graph with stretch factor $ ho =1+2pi(kcos{frac{pi{k)^{-1$ and degree bounded by $k$, for any integer parameter $kgeq 14$. This result immediately implies an algorithm for constructing a planar geometric spanner of a Euclidean graph with stretch factor $ ho cdot C_{del$ and degree bounded by $k$, for any integer parameter $kgeq 14$. Moreover, the resulting spanner contains a Euclidean Minimum Spanning Tree (EMST) as a subgraph. Our second contribution lies in developing the structural results necessary to transfer our analysis and algorithm from Euclidean graphs to unit disk graphs, the usual model for wireless ad-hoc networks. We obtain a very simple distributed, {em strictly-localized algorithm that, given a unit disk graph embedded in the plane, constructs a geometric spanner with the above stretch factor and degree bound, and also containing an EMST as a subgraph. The obtained results dramatically improve the previous results in all aspects, as shown in the paper.

We study the problem of finding the most likely path satisfying a requested additive Quality-of-Service (QoS) value, such as delay. The link metrics are defined as random variables following Weibull probability distributions as empirically reported in [13] and analytically derived in [12]. The problem of finding the most likely path is NP-Hard [24]. Our approach involves reducing the complicated probability convolutions necessary to calculate the most probable path that satisfies a requested delay value. With the reduction of the objective function, an extended Bellman-Ford algorithm is devised to solve the problem. The resulting approach have the same complexity as the standard Bellman-Ford algorithm. Our reduced objective function only needs the location parameter of the Weibull distributions, hence avoiding the complexity of inferring the shape and scale parameters. We evaluate the performance of our approach by simulations and conclude with possible extensions of our work.