Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.     

Extremal problems on triangle areas in two and three dimensions

The study of extremal problems on triangle areas was initiated in a series of papers by Erd?s and Purdy in the early 1970s. In this paper we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles.In the plane, our main result is an O(n44/19)=O(n^2.3158) upper bound on the number of unit-area triangles spanned by n points, which is the first breakthrough improving the classical bound of O(n7/3) from 1992. We also make progress in a number of important special cases. We show that: (i) For points in convex position, there exist n-element point sets that span Ω(nlogn) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most ; there exist n-element point sets (for arbitrarily large n) that span (6/π²−o(1))n² minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span Ω(nlogn) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds).In 3-space we prove an O(n17/7β(n))=O(n^2.4286) upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, O(n8/3), is an old result of Erd?s and Purdy from 1971. We further show, for point sets in 3-space: (i) The number of minimum nonzero area triangles is at most n²+O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span Ω(n4/3) triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is O(n4/3+ε), for any ε>0. (iii) Every set of n points, not all on a line, determines at least Ω(n2/3/β(n)) triangles of distinct areas, which share a common side.     

An optimal algorithm for finding minimal enclosing triangles

Klee and Laskowski's O(n log²n) algorithm for finding all minimal area triangles enclosing a given convex polygon of n vertices is improved to Θ(n), which is shown to be optimal both for finding all minima and for finding just one.     

Empty pseudo-triangles in point sets

We study empty pseudo-triangles in a set P of n points in the plane, where an empty pseudo-triangle has its vertices at the points of P, and no points of P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between Θ(n²) and Θ(n³) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P, this number lies between Θ(n³) and Θ(n⁶). If we count only star-shaped pseudo-triangles, the bounds are Θ(n²) and Θ(n⁵). We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P. If P lies inside a triangle whose corners must be used, we can solve these problems in O(n³) time. In the general case, the running times are O(n⁶) for the maximization problems and O(nlogn) for the minimization problems.     

Triangles of Extremal Area or Perimeter in a Finite Planar Point Set

We show the following two results on a set of n points in the plane, thus answering questions posed by Erdos and Purdy [11]: 1. The maximum number of triangles of maximum area (or of maximum perimeter) in a set of n points in the plane is exactly n . 2. The maximum possible number of triangles of minimum positive area in a set of n points in the plane is Θ(n ² ) . Received April 19, 1999, and in revised form February 29, 2000, and September 12, 2000. Online publication April 6, 2001.     

On a problem of Erdös and Rothschild on edges in triangles

Erdös and Rothschild asked to estimate the maximum number, denoted by h(n, c), such that every n-vertex graph with at least cn ² edges, each of which is contained in at least one triangle, must contain an edge that is in at least h(n, c) triangles. In particular, Erdös asked in 1987 to determine whether for every c > 0 there is ε > 0 such that h(n,c) > n ^ε for all sufficiently large n. We prove that h(n,c) = n ^O(1/loglogn) for every fixed c < 1/4. This gives a negative answer to the question of Erd?s, and is best possible in terms of the range for c, as it is known that every n-vertex graph with more than n ²/4 edges contains an edge that is in at least n/6 triangles.     

Computing optimal islands

Let S be a bicolored set of n points in the plane. A subset I of S is an island if there is a convex set C such that I=C∩S. We give an O(n³)-time algorithm to compute a monochromatic island of maximum cardinality. Our approach is adapted to optimize similar (decomposable) objective functions. Finally, we use our algorithm to give an O(logn)-approximation for the problem of computing the minimum number of convex polygons that cover a class region.     

An elliptic K3 surface associated to Heron triangles

A rational triangle is a triangle with rational sides and rational area. A Heron triangle is a triangle with integral sides and integral area. In this article we will show that there exist infinitely many rational parametrizations, in terms of s, of rational triangles with perimeter 2s(s+1) and area s(s²−1). As a corollary, there exist arbitrarily many Heron triangles with all the same area and the same perimeter. The proof uses an elliptic K3 surface Y. Its Picard number is computed to be 18 after we prove that the Néron-Severi group of Y injects naturally into the Néron-Severi group of the reduction of Y at a prime of good reduction. We also give some constructions of elliptic surfaces and prove that under mild conditions a cubic surface in P³ can be given the structure of an elliptic surface by cutting it with the family of hyperplanes through a given line L. Some of these constructions were already known, but appear to have lacked proof in the literature until now.     

Minimum Covering for Hexagon Triple Systems

A hexagon triple is a graph consisting of three triangles of the form (a, x, b), (b, y, c), and (c,z,a), where a, b, c, x, y, z are distinct. The triangle (a, b, c) is called the inside triangle and the triangles (a, x, b), (b,y,c), and (c, z, a) are called outside triangles. A 3k-fold hexagon triple system of order n is a pair (X, H), where H is an edge-disjoint collection of hexagon triples which partitions the edge set of 3kK ⁿ with vertex set X. Note that the outside triangles form a 3k-fold triple system. If the 3k-fold hexagon triple system (X, H) has the additional property that the inside triangles form a k-fold triple system, then (X, H) is said to be perfect. A covering of 3kK ⁿ with hexagon triples is a triple (X, H, P) such that: 1.3kK ⁿ has vertex set X. 2.P is a subset of E(λ K ⁿ ) with vertex set X for some λ, and 3.H is an edge disjoint partition of E(3kK ⁿ )∪ P with hexagon triples. If P is as small as possible (X, H, P) is called a minimum covering of 3kK ⁿ with hexagon triples. If the inside triangles of the hexagon triples in H form a minimum covering of kK ⁿ with triangles, the covering is said to be perfect. A complete solution for the problem of constructing perfect 3k-fold hexagon triple system and perfect maximum packing of 3kK ⁿ with hexagon triples was given recently by the authors [2]. In this work, we give a complete solution of the problem of constructing perfect minimum covering of 3kK ⁿ with hexagon triples.     

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

Polynomial area bounds for MST embeddings of trees

In their seminal paper on geometric minimum spanning trees, Monma and Suri (1992) [31] showed how to embed any tree of maximum degree 5 as a minimum spanning tree in the Euclidean plane. The embeddings provided by their algorithm require area O(n²²)×O(n²²) and the authors conjectured that an improvement below cn×cn is not possible, for some constant c>0. In this paper, we show how to construct MST embeddings of arbitrary trees of maximum degree 3 and 4 within polynomial area.     

Finding the smallest triangles containing a given convex polygon

For a given convex n-gon P an O(n log²n) algorithm finds all local minima (with respect to area) among the triangles containing P. No areas are computed, for the algorithm is based on a simple geometric characterization of the local minima.     

The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

An Algorithm for the Modular Decomposition of Hypergraphs

We propose an O(n⁴) algorithm to build the modular decomposition tree of hypergraphs of dimension three and show how this algorithm can be generalized to compute in O(n^{3k − 5}) time the decomposition of hypergraphs of any fixed dimension k.     

The Number of Cylindrical Shells

Given a set P of n points in three dimensions, a cylindrical shell (or zone cylinder) is formed by two circular cylinders with the same axis such that all points of P are between the two cylinders. We prove that the number of cylindrical shells enclosing P passing through combinatorially different subsets of P has size (n ³) and O(n ⁴) (the previously known bound was O(n ⁵)). As a consequence, the minimum enclosing shell can be found in O(n ⁴) time.     

On a Heilbronn-type problem

Let F be a convex figure with area |F| and let G(n,F) denote the smallest number such that from any n points of F we can get G(n,F) triangles with areas less than or equal to |F|/4. In this article, to generalize some results of Soifer, we will prove that for any triangle T, G(5,T)=3; for any parallelogram P, G(5,P)=2; for any convex figure F, if S(F)=6, then G(6,F)=4.     

Treewidth computation and extremal combinatorics

For a given graph G and integers b,f ≥0, let S be a subset of vertices of G of size b+1 such that the subgraph of G induced by S is connected and S can be separated from other vertices of G by removing f vertices. We prove that every graph on n vertices contains at most $n\left( {_b^{b + f} } \right)$ such vertex subsets. This result from extremal combinatorics appears to be very useful in the design of several enumeration and exact algorithms. In particular, we use it to provide algorithms that for a given n-vertex graph G

1. compute the treewidth of G in time O(1.7549 ⁿ ) by making use of exponential space and in time O(2.6151 ⁿ ) and polynomial space
2. decide in time O(n ⁵· $_{k + 2}^{\left\lceil {(2n + k + 8)/3} \right\rceil } $ ) if the treewidth of G is at most k
3. list all minimal separators of G in time O(1.6181 ⁿ ) and all potential maximal cliques of G in time O(1.7549 ⁿ ).

This significantly improves previous algorithms for these problems.     

Two-Dimensional and Three-Dimensional Point Location in Rectangular Subdivisions

We apply van Emde Boas-type stratified trees to point location problems in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0, U − 1], we locate an integer query point in O((log log U)^d) query time using O(n) space when d ≤ 2 or O(n log log U) space when d = 3. Applications and extensions of this "fixed universe" approach include spatial point location using logarithmic time and linear space in rectilinear subdivisions having arbitrary coordinates, point location in c-oriented polygons or fat triangles in the plane, point location in subdivisions of space into "fat prisms," and vertical ray shooting among horizontal "fat objects." Like other results on stratified trees, our algorithms run on a RAM model and make use of perfect hashing.     

Approximation algorithms for projective clustering

We consider the following two instances of the projective clustering problem: Given a set S of n points in and an integer k>0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w^* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w^*. This paper contains three main results: (i) For d=2, we present a randomized algorithm that computes O(klogk) strips of width at most w^* that cover S. Its expected running time is O(nk²log⁴n) if k²logkn; for larger values of k, the expected running time is O(n^2/3k^8/3log^14/3n). (ii) For d=3, a cover of S by O(klogk) slabs of width at most w^* can be computed in expected time O(n^3/2k^9/4polylog(n)). (iii) We compute a cover of by O(dklogk) d-cylinders of diameter at most 8w^* in expected time O(dnk³log⁴n). We also present a few extensions of this result.