Minimum-weight triangulation is NP-hard

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$-competitive. However, a Delaunay triangulation ca...

This survey gives a brief overview of theoretically and practically relevant algorithms to compute geodesic paths and distances on three-dimensional surfaces. The survey focuses on polyhedral three-dimensional surfaces.

The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Due to its wide range of applications, the MWISP problem and its special cases have been extensively studied both in the approximation algorithms and the computational geometry community. Despite a lot of research, its gen...

Triangulation graph staining is sufficient for planar graph staining. This article will focus on triangulation and the nature of the color change channel of the staining tool. By construction, the four colors of the vertex are converted into three colors of the side, and two colors of the triangle. Thereby the equivalent dyeing scheme is combined. The color change channel utilizes the transferability of edge dyeing to reflect the integrity of the triangulation graph. Accordin...

Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree spanning trees, which have received significant attention. Let $P = \{p_1,\ldots,p_n\}$ be a set of $n$ points in the plane, let $\Pi$ be the polygonal path $(p_1,\ldots,p_n)$, and let $0 < \alpha < 2\pi$ be an angle. An $\alpha$-spanning tree ($\alpha$-ST) of $P$ is a spanning tree of the complete Euclidean graph o...

In this paper we study minimum cut and maximum flow problems on planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph computes the minimum cut between any two given vertices in O(n log log n) time. Second, we show how to achieve the same O(n log log n) bound for the problem of computing maximum flows in undirected planar graphs. To the best of our knowledge, these are the first algorithms for those two prob...

We present a new game, Dots & Polygons, played on a planar point set. Players take turns connecting two points, and when a player closes a (simple) polygon, the player scores its area. We show that deciding whether the game can be won from a given state, is NP-hard. We do so by a reduction from vertex-disjoint cycle packing in cubic planar graphs, including a self-contained reduction from planar 3-Satisfiability to this cycle-packing problem. This also provides a simple proof...

In this survey article, we are interested on minimal triangulations of closed pl manifolds. We present a brief survey on the works done in last 25 years on the following: (i) Finding the minimal number of vertices required to triangulate a given pl manifold. (ii) Given positive integers $n$ and $d$, construction of $n$-vertex triangulations of different $d$-dimensional pl manifolds. (iii) Classifications of all the triangulations of a given pl manifold with same number of ver...

We describe a new algorithm to compute the geometric intersection number between two curves, given as edge vectors on an ideal triangulation. Most importantly, this algorithm runs in polynomial time in the bit-size of the two edge vectors. In its simplest instances, this algorithm works by finding the minimal position of the two curves. We achieve this by phrasing the problem as a collection of linear programming problems. We describe how to reduce the more general case dow...

We construct a minimum tree for some boundary symmetric tetrahedra R^3, which has two nodes (interior points) with equal weights (positive numbers) having the property that the common perpendicular of some two opposite edges passes through their midpoints. We prove that the length of this minimum tree may have length less than the length of the full Steiner tree for the same boundary symmetric tetrahedra.