Our aim is to approximate the boundary of a set of points, when the number of points is too large to fit into computer memory. We are interested in streaming algorithms: algorithms that compute the approximate convex hull in one pass, and use a small amount of memory. These algorithms have potential applications in data analysis, computer graphics, and unsupervised learning (because approximate convex hulls can be used as a sparse dictionary). We devise lower bounds and algorithms for this problem, some of which work in higher dimensions.
The goal of this paper is to develop a form of functional/persistent arrays that can be used in parallel. If A is a functional array [0, 1, 2], then update(A, index=1, value=7) returns [0, 7, 2] but does not modify A. We allow operations on “old” arrays to be more expensive than on “new” arrays. Our main contributions are 1. Providing a functional interface while safely dealing with concurrent effects under the hood, and 2. Giving a deterministic way to bound the costs even though the actual costs depend on the interleaving of execution threads. We give a proof for our implementation and cost bounds.
Making a Tree Bridge-Free by adding Minimal Edges (paper)
Our aim is to add the minimal number of edges to a given tree so that it is bridge-free. This is a solved problem, however we present a simpler construction, and show that our algorithm can generate all possible solutions. We also give novel near linear time algorithms for two special cases of the NP-complete weighted version of the problem. In our variants, the cost of adding an edge between two vertices is the sum of the weights of edges on the (unique) path between the two vertices. We prove an algorithm that makes the tree bridge free with minimal cost incurred, and an algorithm that adds the minimal number of edges to make the graph bridge-free, while maximizing the incurred cost.