Dynamic Algorithms in Computational Geometry

Dynamic Algorithms in Computational Geometry; Li; date

This is a survey paper of dynamic algorithms available for a variety of geometric problems, including nearest neighbor.  For Voronoi diagrams, Li describes Mumuley's algorithm for diagrams of order 1 to \(k\) in \(R^d\) .  Expected time for \(d=2\) in a random \((N,\delta)\) -sequence is \(O(k^2 + \log n)\) .  For \(d > 2, O(k^{\lceil d/2\rceil + 2} n^{\lceil d/2 \rceil -1})\) .

In the 2-dimensional case, the query time is \(O(k \log^2 n)\) and update time is \(O(k^2 + \log n)\) .  Similarly for 3-dimensions, query time is \(O(k \log^2 n)\) and update time is \(O(k^4 n \log^2 n)\) .

Mumuley. Computational Geometry: an introduction through randomized algorithms. 1994, Prentice-Hall Inc.

Leave a Comment

Filed under Algorithms, Voronoi Diagrams

Generalized Voronoi Diagram Updating

Improved Updating of Euclidean Distance Maps and Voronoi Diagrams; Lau, Sprunk, Burgard; date

Primarily focuses on the Generalized Voronoi Diagram as used in navigation for robotics.  Diagrams are represented on grid maps.

Leave a Comment

Filed under Algorithms, Voronoi Diagrams

Interactive Analysis Using Voronoi Diagrams

Interactive analysis using voronoi diagrams: Algorithms to support dynamic update from a generic triangle-based data structure; Lee, Gahegan; 2002

Describe methods for updating five types of Voronoi diagrams using a data structure that stores the Delaunay triangulation of a given pointset.  For Ordinary Vornoi Diagrams (OVD), edge swapping is used to dynamically insert points in \(O(n)\) time.  To remove points, Ing's 1993 reversion algorithm is used, with worst case \(O(n)\) time.

Leave a Comment

Filed under Algorithms, Voronoi Diagrams

Dynamic Voronoi Diagrams

Dynamic Voronoi Diagrams; Gowda, Kirkpatrick, Lee, Naamad; 1983

First note that dynamically updating a Voronoi diagram by adding or removing one point can change as many as \(\Theta(n)\) edges in the worst case, therefore no worst-case-sublinear algorithms exist.  They present an algorithm that is \(O(n)\) for both insert and delete, using a V-tree (Voronoi tree) design.

Each leaf of the tree stores a point in the given pointset \(S\) .  Internal nodes \(x\) store the Voronoi diagram \(VOD(sub(x))\) for the subtree rooted at \(x\) .  This requires \(O(nh)\) storage, where \(h\) is the height of the tree, but may be reduced to \(O(n \log \log n)\) and preserving linear update time.


Consider the \(k\) -minimum spanning circle problem: Given a planar point set \(S=\{(x_j, y_j) | 1 \le j \le n\}\) where \(n > k\) , find \(k\) circles that every point in \(S\) is contained in at least one circle and the largest circle is minimized.

Leave a Comment

Filed under Algorithms, Voronoi Diagrams

Assessing the comparative Effectiveness of Newly Marketed Medications: Methodological challenges and Implications for Drug Development


This paper is from Jeremy's group in Harvard.

Comparative-effectiveness research is discussed, which is "using secondary health-care data, including EMRs, longitudinal claims data, and regstries" to study the outcomes of medicines in the normal routine of medical practice without intervening in the delivery of the care that produces these outcomes. (Why useful? see Figure 1)


Leave a Comment

Filed under Medical, Propensity Scores

Li's Dissertation 2011


Li describes the brute force method for matching participants in 4 groups on page 35. It will be of note to examine the C code to see how he performs this matching. Their suboptimal matching also falls prey to the 7th son example, in that matchings are optimal for points in group 1, but not across the other groups.

Upon further searching, I can find neither their R package nor C code.

Research Question: The biggest hurdle to the Lu group's research seems to be this suboptimal matching.  That is, they can't do an optimal matching across more than two groups.  Therefore, they do an optimal bipartite matching or an optimal pair-matching between group 1 and the other k-1 groups individually, then match in on group 1.  Each of these approaches are considered suboptimal; for example, the latter does not guarantee best matches between groups 2 and 3. Could we create an optimal matching across multiple groups? To test this, it would be advantageous to get an actual dataset.


Leave a Comment

Filed under Propensity Scores

Propensity Scores 2


This is likely the best and most comprehensive and easy to follow discussion on propensity scores that I have seen yet. Multiple examples are considered.

Starting on page 12, the author goes into a deeper discussion on matching, including nearest neighbor matching.  Page 20 provides the best evidence for matching (and a description of it) that I've seen, comparing both un-matched and matched controls to the "treatment" (drug use) group.

Most matchings consider a larger control group than a treated group.  Gu and Rosenbaum (1993: 413) note that optimal algorithms and greedy (go through the treatment group G1 only once and assign best matches) algorithms pick roughly the same controls, but may not assign them to the best matches between the two groups.

Research Question: Our matching algorithm, how would it perform under a greedy assumption vs the current "smallest first" nearest-neighbors approach?  Again, what would an optimal (smallest total sum of distances) approach look like? What about increasing the size of the control group (assume Gk) to 2n participants and matching to the best n? How about allowing multiple controls/matches per treated---how will that affect our outcome? [These questions may need actual data. Perhaps use Stuart's data from this talk, if available, to compare?]


  • Existing packages for matching [twang (McCaffrey), Matching (Sekhon), MatchIt (Ho)]
  • Paper References: (Smith 1997, Rubin and Thomas 2000)
  • Multilevel settings (see slide 155, p38)
  • MatchIt R package for matching (http://gking.harvard.edu/matchit)
  • Stuart's website: www.biostat.jhsph.edu/~estuart

Leave a Comment

Filed under Propensity Scores

Propensity Score Primer


Lu presents an example of and uses for Propensity scores. Full PSM model on slides 47-48.

Slide 28 describes the need for pair matching, as we expanded to k-way matching for our kd tree paper.

Research Question: can we extend the kd-tree algorithm to an optimal matching approach (minimizing the sum of the distances)? According to Lu, this approach provides a better matching than the nearest-neighbor approach (see slides 33-39).

Further studies:

Leave a Comment

Filed under Propensity Scores

Initial Setup

So, since I am scouring for ideas and reading many interesting papers, I figured I needed a place to collect this data.

Why not a Word document, etc?  Well, I wanted a place to update and add summaries from all my devices and to easily access them from any other device.  This seemed like the most appropriate method of collecting, sorting, and sharing these ideas.

Leave a Comment

Filed under Uncategorized