11

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem. Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987. Satish ...


10

FIRST ARGUMENT: This was my first answer. Note that this argument is wrong. See my second argument below. I don't think it's true. The reason that it works in the plane is that in a circle, the inscribed angle subtended by a chord is one half the corresponding central angle. Thus, if we have a triangle with a small angle, any points that would make a larger ...


8

The first approach can be formalized as follows. Let $P$ be an arbitrary set of $n$ points on the positive branch of the parabola $y=x^2$; that is, $$ P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \} $$ for some positive real numbers $t_1, t_2, \dots, t_n$. Without loss of generality, assume these points are indexed in increasing order: $0 < ...


8

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.


7

Yes. See Dillencourt, Michael B.; Smith, Warren D. Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161 (1996), no. 1-3, 63–77. However, if a topological triangulation has no separating triangles, and no chords connecting pairs of vertices on its outer face, then it is always realizable as a Delaunay triangulation....


5

Testing whether a pair of points $p_i$ and $p_j$ are the endpoints of a Delaunay edge can be solved as a linear programming feasability problem: Lift each point to one higher dimension by making its last coordinate be the sum of squares of the other coordinates. Then look for a hyperplane passing through $p_i$ and $p_j$, such that all the other points are on ...


5

(In 2-space,) a Delaunay triangulation is a planar graph. All planar graphs have average degree at most 6. So, many (all?) operations that depend on vertex degree of a Delaunay triangulation will run in $O(1)$ expected time.


2

Here's a theta bound on the expected value of the maximum degree of any vertex in a DT: $\Theta (\log n / \log \log n)$ Here's the paper: http://www.ics.uci.edu/~eppstein/pubs/BerEppYao-IJCGA-91.pdf. If anyone else finds other properties, let me know!


2

Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper: A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.


1

I think only those vertices corresponding to triangles sharing an edge with boundary or holes of the polygon will be of degree less than 3. Now the number of triangles in the triangulation is fixed. So you can always get the exact ratio of the number of degree 3 vertices for a polygon. If the polygon has $k$ vertices and $l$ holes vertices and the number of ...


1

The following algorithm might help. 1. Choose any vertex from the graph. 2. Do a BFS untill $O(K)$ vertices has been visited. 3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster). 4. Remover the visited vertices from the graph. 5. Repeat 1-4 untill all nodes are visited. Every cluster contains $O(K)$ vertices and ...


1

One natural thing would be to try a separator kind of trick. If the Voronoi cells are fat, and of similar size then a randomly shifted grid of the right side would do reasonably well. in particular, there is a paper by Miller and Thurston (and some other people - their names escape me) about finding a separator if you have fat regions covering space, and ...


Only top voted, non community-wiki answers of a minimum length are eligible