First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. For a positive integer parameter t , in O ( tm ) time the algorithm finds for each vertex v a path distance from the source to v not exceeding that given by the shortest path from the source to v among the so called t + light paths . A directed path between two vertices is t + light if it contains at most t more edges than the minimum edge-cardinality directed path between these vertices. For t = O ( n ) , our algorithm yields an O ( nm )-time solution to SSSP in directed graphs with real edge weights matching the time complexity of the Bellman-Ford algorithm. Our next contribution is a new algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input DAG. If the number of leaves is sufficiently small on the average, the algorithm is substantially faster than the best known algorithm in case of non-sparse DAGs. We also discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

Abstract We study applications of clustering (in particular, the Hamming k -center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). We provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $${\ell }$$ ℓ -center clustering of the rows of the first matrix or an k -center clustering of the columns of the second matrix. We use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an alternative simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $${\ell }$$ ℓ - and k -center clustering.

We consider the fundamental problem of assigning distinct labels to agents in theprobabilistic model of population protocols. Our protocols operate under the assumptionthat the size n of the population is embedded in the transition function. W.h.p. (withhigh probability), they are silent, i.e., eventually each agent reaches its nal state andremains in it forever, and they are safe, i.e., never change a label that has already beenassigned to an agent. We provide efficient protocols for this problem complemented withtight lower bounds. Our fast labeling protocol uses only O((n logn)/ε) interactions w.h.p.,(2 + ε)n + O(na) states, and the label range [1,(1 + ε)n], where 1 ≥ ε > 0 and 0 < a < 1,while our nearly state-optimal protocol uses only n + 5√n + O(log logn) states, the labelrange [1,n], and w.h.p., O(n3) interactions.

We study the problems of computing the Voronoi diagram and a triangulation of a set of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane in a substantially sublinear in n number of rounds in the congested clique model with n nodes. First, we observe that if the points are uniformly at random distributed in a unit square then their Voronoi diagram within the square can be computed in O ( 1 ) rounds with high probability (w.h.p.). Next, we show that if a very weak smoothness condition is satisfied by an input set of n 2 points with O ( log ⁡ n ) -bit coordinates in the unit square then the Voronoi diagram of the point set within the unit square can be deterministically computed in O ( log ⁡ n ) rounds in this model. Finally, we present a deterministic O ( log ⁡ n ) -round protocol for a triangulation of n 2 points with O ( log ⁡ n ) -bit coordinates in the Euclidean plane. It relies on our novel method for extending triangulations of two planar point sets separated by a straight line to a complete triangulation of the union of the sets in O ( 1 ) rounds.

We study the time complexity of computing the ( min ⁡ , + ) matrix product of two n × n integer matrices in terms of n and the number of monotone subsequences the rows of the first matrix and the columns of the second matrix can be decomposed into. In particular, we show that if each row of the first matrix can be decomposed into at most m 1 monotone subsequences and each column of the second matrix can be decomposed into at most m 2 monotone subsequences such that all the subsequences are non-decreasing or all of them are non-increasing then the ( min ⁡ , + ) product of the matrices can be computed in O ( m 1 m 2 n 2.569 ) time. On the other hand, we observe that if all the rows of the first matrix are non-decreasing and all columns of the second matrix are non-increasing or vice versa then this case is as hard as the general one. We also present six cases of the restrictions on the input integer matrices under which the problem of computing the ( min ⁡ , + ) matrix product is equally hard as that of computing the minimum and maximum witnesses of Boolean matrix product. Similarly, we also study the time complexity of computing the ( min ⁡ , + ) convolution of two n -dimensional integer vectors in terms of n and the number of monotone subsequences the two vectors can be decomposed into. We show that if the first vector can be decomposed into at most m 1 monotone subsequences and the second vector can be decomposed into at most m 2 subsequences such that all the subsequences of the first vector are non-decreasing and all the subsequences of the second vector are non-increasing or vice versa then their ( min ⁡ , + ) convolution can be computed in O ˜ ( m 1 m 2 n 1.5 ) time. On the other, the case when both vectors are non-decreasing or both of them are non-increasing is as hard as the general case. Finally, we present six cases of the restrictions on the input integer vectors under which the problem of computing the ( min ⁡ , + ) vector convolution is equally hard as that of computing the minimum and maximum witnesses of the Boolean vector convolution.

The parallel time of a population protocol is defined as the average number of required interactions in which an agent in the protocol participates, i.e., the quotient between the total number of interactions required by the protocol and the total number n of agents, or just roughly the number of required rounds, where a round stands for a sequence of n consecutive interactions. This naming triggers an intuition that at least the expected number of parallel steps sufficient to implement a round is O(1). In a single parallel step only mutually independent interactions can be involved. We show that when the transition function of a population protocol is treated as a black box then the expected maximum number of parallel steps necessary to implement a round is Ω(log⁡nlog⁡log⁡n). We also provide a combinatorial argument for a matching upper bound on the expected number of parallel steps under additional assumptions. Further, we extend these bounds by showing that the situation changes dramatically for sequences of m=Ω(nlog⁡n) interactions. Then, the expected number of parallel steps required to implement such sequences is Θ(mn) under the aforementioned additional assumptions. Thus, it asymptotically coincides with the notion of parallel time, i.e., O(mn), for sequences of interactions produced by protocols solving any non-trivial problems requiring Ω(nlog⁡n) interactions.

Let NDTIME(f(n),g(n)) denote the class of problems solvable in O(g(n)) time by a multi-tape Turing machine using an f(n)-bit non-deterministic oracle, and let DTIME(g(n)) = NDTIME(0, g(n)). We show that if the all-pairs shortest paths problem (APSP) for directed graphs with N vertices and integer edge weights within a super-exponential range { −2Nk+o(1),....,2Nk+o(1) }, k≥1 does not admit a truly subcubic algorithm then for any ∈>0, NDTIME([ 1/2 log2 n ], n)⊆DTIME(n1+12+k−∈). If the APSP problem does not admit a truly subcubic algorithm already when the edge weights are of moderate size then we obtain an even stronger implication, namely that for any ∈>0, NDTIME([ 1/2 log2 n ], n)⊆DTIME(n1.5−∈). Similarly, we show that if the triangle detection problem (DT) in a graph on N vertices does not admit a truly sub-Nω -time algorithm then for any ∈>0, NDTIME([ 1/2 log2 n ], n)⊆DTIME(nw/2−∈), where ω stands for the exponent of fast matrix multiplication. For the more general problem of detecting a minimum weight ℓ-clique (MWCℓ) in a graph with edge weights of moderate size, we show that the non-existence of truly sub−Nℓ−time algorithm yields for any ∈>0, NDTIME((ℓ−2)[ 12 log2n ],n)⊆DTIME(n1+ℓ−22−∈). Next, we show that if 3SUM for N integers in { −2Nk+o(1),....2Nk+o(1) } for some k≥0, does not admit a truly subquadratic algorithm then for any ∈>0, NDTIME([ log2n ],n)⊆DTIME(n1+11+k−∈). Finally, we observe that the Exponential Time Hypothesis (ETH) implies NDTIME([ k log2n ],n)⊆DTIME(n) for some k>0, while the strong ETH (SETH) yields for any ∈>0, NDTIME([ log2n ],n)⊆DTIME(n2−ε). For comparison, the strongest known result on separation between non-deterministic and deterministic time only asserts NDTIME(O(n),n)⊆DTIME(n).

We consider the fundamental problem of assigning distinct labels to agents in the probabilistic model of population protocols. Our protocols operate under the assumption that the size n of the population is embedded in the transition function. Their efficiency is expressed in terms of the number of states utilized by agents, the size of the range from which the labels are drawn, and the expected number of interactions required by our solutions. Our primary goal is to provide efficient protocols for this fundamental problem complemented with tight lower bounds in all the three aspects. W.h.p. (with high probability), our labeling protocols are silent, i.e., eventually each agent reaches its final state and remains in it forever, and they are safe, i.e., never update the label assigned to any single agent. We first present a silent w.h.p. and safe labeling protocol that draws labels from the range [1,2n]. Both the number of interactions required and the number of states used by the protocol are asymptotically optimal, i.e., O(n log n) w.h.p. and O(n), respectively. Next, we present a generalization of the protocol, where the range of assigned labels is [1,(1+ε) n]. The generalized protocol requires O(n log n / ε) interactions in order to complete the assignment of distinct labels from [1,(1+ε) n] to the n agents, w.h.p. It is also silent w.h.p. and safe, and uses (2+ε)n+O(n^c) states, for any positive c < 1. On the other hand, we consider the so-called pool labeling protocols that include our fast protocols. We show that the expected number of interactions required by any pool protocol is ≥ (n²)/(r+1), when the labels range is 1,… , n+r < 2n. Furthermore, we provide a protocol which uses only n+5√ n +O(n^c) states, for any c < 1, and draws labels from the range 1,… ,n. The expected number of interactions required by the protocol is O(n³). Once a unique leader is elected it produces a valid labeling and it is silent and safe. On the other hand, we show that (even if a unique leader is given in advance) any silent protocol that produces a valid labeling and is safe with probability > 1-(1/n), uses ≥ n+√{(n-1)/2}-1 states. Hence, our protocol is almost state-optimal. We also present a generalization of the protocol to include a trade-off between the number of states and the expected number of interactions. Finally, we show that for any silent and safe labeling protocol utilizing n+t < 2n states, the expected number of interactions required to achieve a valid labeling is ≥ (n²)/(t+1).

We consider Boolean circuits over {or, and, neg} with negations applied only to input variables. To measure the "amount of negation" in such circuits, we introduce the concept of their "negation width". In particular, a circuit computing a monotone Boolean function f(x_1,...,x_n) has negation width w if no nonzero term produced (purely syntactically) by the circuit contains more than w distinct negated variables. Circuits of negation width w=0 are equivalent to monotone Boolean circuits, while those of negation width w=n have no restrictions. Our motivation is that already circuits of moderate negation width w=n^{epsilon} for an arbitrarily small constant epsilon>0 can be even exponentially stronger than monotone circuits. We show that the size of any circuit of negation width w computing f is roughly at least the minimum size of a monotone circuit computing f divided by K=min{w^m,m^w}, where m is the maximum length of a prime implicant of f. We also show that the depth of any circuit of negation width w computing f is roughly at least the minimum depth of a monotone circuit computing f minus log K. Finally, we show that formulas of bounded negation width can be balanced to achieve a logarithmic (in their size) depth without increasing their negation width.

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., the maximum number of and-gates on a directed path to an output gate). In particular, we show that any normalized Boolean circuit of at most epsilon log n conjunction-depth computing the n-dimensional Boolean vector convolution has Omega(n^{2-4 epsilon}) and-gates. Analogously, any normalized Boolean circuit of at most epsilon log n conjunction-depth computing the n x n Boolean matrix product has Omega(n^{3-4 epsilon}) and-gates. We complete our lower-bound trade-offs with upper-bound trade-offs of similar form yielded by the known fast algebraic algorithms.

We study the problem of computing the so called minimum and maximum witnesses for Boolean vector convolution. We also consider a generalization of the problem which is to determine for each positive value at a coordinate of the convolution vector, q smallest (largest) witnesses, where q is the minimum of a parameter k and the number of witnesses for this coordinate. We term this problem the smallest k-witness problem or the largest k-witness problem, respectively. We also study the corresponding smallest and largest k-witness problems for Boolean matrix product. First, we present an $$\tilde{O}(n^{1.5}k^{0.5})$$ -time algorithm for the smallest or largest k-witness problem for the Boolean convolution of two n-dimensional vectors, where the notation $$\tilde{O}(\ )$$ suppresses polylogarithmic in n factors. In consequence, we obtain new upper time bounds on reporting positions of mismatches in potential string alignments and on computing restricted cases of the $$(\min , +)$$ vector convolution. Next, we present a fast (substantially subcubic in n and linear in k) algorithm for the smallest or largest k-witness problem for the Boolean matrix product of two $$n\times n$$ Boolean matrices. It yields fast algorithms for reporting k lightest (heaviest) triangles in a vertex-weighted graph.

We study a capacitated network design problem in a geometric setting. The input consists of an integral edge capacity $k$ and two sets of points on the Euclidean plane, sources, and sinks, with an integral demand for each point. The demand of each source specifies the amount of flow that has to be shipped from the source, and the demand of each sink specifies the amount of flow that has to be shipped to the sink. The goal is to construct a minimum-length network that allows one to route the requested flow from the sources to the sinks and where each edge in the network has capacity $k$. The vertices of the network are not constrained to the sets of sinks and sources---any point on the Euclidean plane can be used as a vertex. The flow is splittable and parallel edges are allowed. The capacitated geometric network design problem generalizes, among others, the geometric Steiner tree problem, and as such it is NP-hard. We show that if the demands are polynomially bounded and the edge capacity $k$ is not too large, the single-sink capacitated geometric network design problem admits a polynomial time approximation scheme. If the capacity is arbitrarily large, then we design a quasi-polynomial time approximation scheme for the capacitated geometric network design problem allowing for an arbitrary number of sinks. Our results rely on a derivation of an upper bound on the number of vertices different from sources and sinks (the so-called Steiner vertices) in an optimal network. The bound is polynomial in the total demand of the sources.

We study the problem of efficiently correcting an erroneous product of two $$n\times n$$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in $${\tilde{O}}(n^2+kn)$$ time and a deterministic $${\tilde{O}}(kn^2)$$ -time algorithm for this problem (where the notation $${\tilde{O}}$$ suppresses polylogarithmic terms in n and k).

We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.

We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let $H$ be a fixed graph with $k$ vertices and an independent set of size $s.$ 1. Detecting if an $n$-vertex graph contains a (not necessarily induced) subgraph isomorphic to $H$ can be done in time $O(n^{\omega(\lceil (k-s)/2 \rceil, 1, \lfloor (k-s)/2 \rfloor )})$, where $\omega (p,q,r)$ is the exponent of fast arithmetic matrix multiplication of an $n^p\times n^q$ matrix by an $n^q\times n^r$ matrix. 2. When $s=2,$ counting the number of (not necessarily induced) subgraphs isomorphic to $H$ can be done in the same time, i.e., in time $O(n^{\omega(\lceil (k-2)/2 \rceil, 1, \lfloor (k-2)/2 \rfloor )}).$ It follows in particular that we can count the number of subgraphs isomorphic to any $H$ on four vertices that is not $K_4$ in time $O(n^{\omega})$, where $\omega =\omega (1,1,1)$ is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any $H$ on five vertices that is not $K_5$ in time $O(n^{\omega(2,1,1)}),$ where $\omega(2,1,1)$ is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number $m$ of edges of the input graph and do not rely on fast matrix multiplication.

A recursive algorithm by Aho et al. [SIAM J. Comput., 10 (1981), pp. 405–421] forms the basis for many modern rooted supertree methods employed in Phylogenetics. However, as observed by Bryant [Building Trees, Hunting for Trees, and Comparing Trees: Theory and Methods in Phylogenetic Analysis, Ph.D. thesis, University of Canterbury, Christchurch, New Zealand, 1997], the tree output by the algorithm of Aho et al. is not always minimal; there may exist other trees which contain fewer nodes yet are still consistent with the input. In this paper, we prove strong polynomial-time inapproximability results for the problem of inferring a minimally resolved supertree from a given consistent set of rooted triplets (MinRS). Furthermore, we show that the decision version of MinRS is NP-hard for any fixed positive integer $q\geq4$, where q is the number of allowed internal nodes, but linear-time solvable for $q\leq3$. In contrast, MinRS becomes polynomial-time solvable for any q when restricted to caterpillars. We also present an exponential-time algorithm based on tree separators for solving MinRS exactly. It runs in $2^{O(n\log p)}$ time when every node may have at most p children that are internal nodes and where n is the cardinality of the leaf label set. Finally, we demonstrate that augmenting the algorithm of Aho et al. with an algorithm for optimal graph coloring to help merge certain blocks of leaves during the execution does not improve the output solution much in the worst case.

We present a general technique for detecting and counting small subgraphs.It consists in forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph.The combinations can be efficiently computed by rectangular matrix multiplication.Our two main results utilizing the technique are as follows.Let H be a fixed graph with k vertices and an independent set of size s.1. Detecting if an n-vertex graph contains a (nonnecessarily induced) subgraph isomorphic to H can be done in timewhere ω(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n p × n q matrix by an n q × n r matrix.2. When s = 2, counting the number of (nonnecessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n k-2 + n ω( (k-2)/2 ,1, (k-2)/2 ) ). (This improves for s = 2 on a counting algorithm of Vassilevska and Williams, running in time O(n k-s+3 ).)It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K 4 in time O(n ω ), where ω = ω(1, 1, 1) is known to be smaller than 2.376.Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K 5 in time O(n ω(2,1,1) ), where ω(2, 1, 1) is known to be smaller than 3.334.

We study broadcasting (one-to-all communication) in known topology radio networks modeled by graphs, where the interference range of a node is likely to exceed its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge their transmissions disable recipience of one another. For a network G, we term the smallest integer d, s.t., for any interference edge e there exists a simple path formed of at most d transmission edges connecting the endpoints of e as its interference distance dI. In this model the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on limited number of transmissions at each node.

We show that a maximum-weight triangle in an undirected graph with n vertices and real weights assigned to vertices can be found in time $\mathcal{O}(n^{\omega}+n^{2+o(1)})$, where $\omega$ is the exponent of the fastest matrix multiplication algorithm. By the currently best bound on $\omega$, the running time of our algorithm is $\mathcal{O}(n^{2.376})$. Our algorithm substantially improves the previous time-bounds for this problem, and its asymptotic time complexity matches that of the fastest known algorithm for finding any triangle (not necessarily a maximum-weight one) in a graph. We can extend our algorithm to improve the upper bounds on finding a maximum-weight triangle in a sparse graph and on finding a maximum-weight subgraph isomorphic to a fixed graph. We can find a maximum-weight triangle in a vertex-weighted graph with m edges in asymptotic time required by the fastest algorithm for finding any triangle in a graph with m edges, i.e., in time $\mathcal{O}(m^{1.41})$. Our algorithms for a maximum-weight fixed subgraph (in particular any clique of constant size) are asymptotically as fast as the fastest known algorithms for a fixed subgraph.

The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial timeapproximation scheme for max-bisection on unit disk graphs (which could also be easily extended to other geometrically defined graphs).

The problem of performing t tasks in a distributed system on p failure-prone processors is one of the fundamental problems in distributed computing. If the tasks are similar and independent and the processors communicate by sending messages then the problem is called Do-All. In our work the communication is over a multiple-access channel, and the attached stations may fail by crashing. The measure of performance is work, defined as the number of the available processor steps. Algorithms are required to be reliable in that they perform all the tasks as long as at least one station remains operational. We show that each reliable algorithm always needs to perform at least the minimum amount Ω(t + p√t) of work. We develop an optimal deterministic algorithm for the channel with collision detection performing only the minimum work Θ(t + p√t). Another algorithm is given for the channel without collision detection, it performs work O(t + p√t + p · min {f, t}), where f < p is the number of failures. It is proved to be optimal if the number of faults is the only restriction on the adversary. Finally we consider the question if randomization helps for the channel without collision detection against weaker adversaries. We develop a randomized algorithm which needs to perform only the expected minimum work if the adversary may fail a constant fraction of stations, but it has to select the failure-prone stations prior to the start of an algorithm.

For a polygon P, the bounded Voronoi diagram of P is a partition of P into regions assigned to the vertices of P: A point p inside P belongs to the region of a vertex v if and only if v is the closest vertex of P visible from p. We present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Among other applications, we can construct within the same time bound the generalized Delaunay triangulation of P and the minimal spanning tree on P 's vertices that is contained in P.

Let P be a simple planar polygon. We present a linear worst-case time algorithm for constructing the bounded Voronoi diagram of P in the Manhattan metric, where each point z in P belongs to the region of the closest vertex of P that is visible from z. Among other consequences, the minimal spanning tree of the vertices in the Manhattan metric that is contained in P can be computed within optimal linear time.

Manacher and Zorbrist conjectured that the greedy triangulation heuristic for minimum weight triangulation of n-point planar point sets yields solutions within an Ο(nε), ε < 1, factor of the optimum. We prove the conjecture in the case when the point set is convex by finding basic, geometric and combinatoric properties of greedy triangulations in the convex case. Our result contrasts with Kirkpatrick's Ω(n) bound on the approximation factor of the Delauney triangulation heuristic which holds for convex, planar n-point sets. To support the conjecture of Manacher and Zorbrist, we also show that the greedy triangulation heuristic for minimum weight triangulation of a (non-necessarily convex) polygon yields solutions at most h times longer than the optimum where h is the diameter of the tree dual to the produced greedy triangulation of the polygon. On the other hand, we present an implementation of the greedy triangulation heuristic for an n-vertex convex point set or a convex polygon taking Ο(n2) time and Ο(n) space which improves Gilbert's Ο(n2logn)-time and Ο(n2)-space bound in this case. To derive the latter result, we show that given a convex polygon P, one can find for all vertices v of P a shortest diagonal of P incident to v in linear time.

Chaselle has shown how to partition any simple polygon P into two polygons, each of total weight not greater than two thirds of the total weight of P, by drawing a diagonal within P. Under the assumption that a triangulation of P is given, we provide a straightforward proof of Chaselles theorem and derive generalizations of the theorem to include polygons with polygonal holes.