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
Abstract
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.
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.
Last update: May 8, 2009.