Günter Rote and André Schulz:

Resolving loads with positive interior stresses

In: Algorithms and Data Structures Symposium-WADS 2009, Banff, August 2009, Editors: Frank Dehne, Ian Munro, Jörg-Rüdiger Sack, and Roberto Tamassia, Lecture Notes in Computer Science, 5664, Springer-Verlag, 2009, pp. 530–541. doi:10.1007/978-3-642-03367-4_46


We consider the pair (pi, fi) as a force with two-dimensional direction vector fi applied at the point pi in the plane. For a given set of forces we ask for a non-crossing geometric graph on the points pi that has the following property: there exists a weight assignment to the edges of the graph, such that for every pi the sum of the weighted edges (seen as vectors) around pi yields −fi. As additional constraint we restrict ourselves to weights that are non-negative on every edge that is not on the convex hull of the point set. We show that (under a generic assumption) for any reasonable set of forces there is exactly one pointed pseudo-triangulation that fulfils the desired properties. Our results will be obtained by linear programming duality over the PPT-polytope. For the case where the forces appear only at convex hull vertices we show that the pseudo-triangulation that resolves the load can be computed as weighted Delaunay triangulation. Our observations lead to a new characterization of pointed pseudo-triangulations, structures that have been proven to be extremely useful in the design and analysis of efficient geometric algorithms.

As an application, we discuss how to compute the maximal locally convex function for a polygon whose corners lie on its convex hull. This extends results that were presented in the earlier paper A pointed Delaunay pseudo-triangulation of a simple polygon mentioned below.

Our studies are motivated by the construction of discrete Laplace-Beltrami operators.

  pdf file (gzipped)

Günter Rote and André Schulz:

A pointed Delaunay pseudo-triangulation of a simple polygon

In: Abstracts of the 21st European Workshop on Computational Geometry, Eindhoven, March 2005, pp. 77-80.
  pdf file (gzipped)
other papers about this subject
Last update: May 8, 2009.