# Farthest neighbors and triangle strips

Two new papers:

"Approximate Weighted Farthest Neighbors and Minimum Dilation Stars", with John Augustine (newly blogging at

I also added a new pub list entry for "Single Triangle Strip and Loop on Manifolds with Boundaries", with Anusheel Bhushan, Pablo Diaz-Gutierrez, and M. Gopi, a technical report following on to my previous paper with Gopi on finding single-strip triangulations of polyhedral models without boundaries.

"Approximate Weighted Farthest Neighbors and Minimum Dilation Stars", with John Augustine (newly blogging at

**augblog**— what a good name!) and Kevin Wortman, just went up on arXiv. The problem is to quickly find, in a set of sites with weights, the site maximizing the product of its weight with its distance from the query point. Our solution combines known results on core-sets with a reduction from the weighted to the unweighted problem that works in any metric space; we solve the problem in logarithmic time in any fixed dimension and with any constant approximation ratio. As the title suggests, we apply this data structure to the minimum dilation star problem from Kevin's SoCG'05 paper.I also added a new pub list entry for "Single Triangle Strip and Loop on Manifolds with Boundaries", with Anusheel Bhushan, Pablo Diaz-Gutierrez, and M. Gopi, a technical report following on to my previous paper with Gopi on finding single-strip triangulations of polyhedral models without boundaries.