On the Maximum Number of Equilateral Triangles, I

The following problem was posed by Erdős and Purdy: ``What is the maximum number of equilateral triangles determined by a set of n points in R ^d ?' New bounds for this problem are obtained for dimensions 2, 4, and 5. In addition it is shown that for d=2 the maximum is attained by subsets of the regular triangle lattice. Received April 9, 1998, and in revised form October 30, 1998.     

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.     

On the Number of Balanced Lines

Given a set of n black and n white points in general position in the plane, a line l determined by them is said to be balanced if each open half-plane bounded by l contains precisely the same number of black points as white points. It is proved that the number of balanced lines is at least n . This settles a conjecture of George Baloglou. Received August 1, 2000, and in revised form October 23, 2000. Online publication April 6, 2001.     

The Number of Isosceles Right Triangles Determined by <Emphasis Type="Italic">n</Emphasis> Points in Convex Position in the Plane

Any set of n points in convex position in the plane induces at most 2n congruent copies of a fixed isosceles triangle. Furthermore, at most 2n–4 congruent isosceles right triangles can be induced by a set of n points in convex position, and in strictly convex position at most n congruent isosceles right triangles can be induced.     

Maintaining the Extent of a Moving Point Set

Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of S . If the points in S move with algebraic motions, these structures process O(n ^2+\eps ) events. We also give constructions showing that Ω(n ² ) combinatorial changes are possible for these extent functions even if each point is moving with constant velocity. We give a similar construction and upper bound for the convex hull, improving known results. Received April 25, 2000, and in revised form September 25, 2000. Online publication May 4, 2001.     

Isoperimetric triangular enclosures with a fixed angle

In this paper, we study four variants of the famous isoperimetric problem. Given a set S of n > 2 points in the plane (in general position), we show how to compute in O(n ²) time, a triangle with maximum (or minimum) area enclosing S among all enclosing triangles with fixed perimeter and one fixed angle. We also show how to compute in O(n ²) time, a triangle with maximum (or minimum) perimeter enclosing S among all enclosing triangles with fixed area and one fixed angle. We also provide an Ω (n log n) lower bound for these problems in the algebraic computation tree model.     

An Improved Bound on the Number of Unit Area Triangles

We show that the number of unit-area triangles determined by a set of n points in the plane is O(n ^9/4+ε ), for any ε>0, improving the recent bound O(n ^44/19) of Dumitrescu et al.     

Almost Disjoint Triangles in 3-Space

Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n ^3/2 ) .     

Triangles in Euclidean Arrangements

The number of triangles in arrangements of lines and pseudolines has been the object of some research. Most results, however, concern arrangements in the projective plane. In this article we add results for the number of triangles in Euclidean arrangements of pseudolines. Though the change in the embedding space from projective to Euclidean may seem small there are interesting changes both in the results and in the techniques required for the proofs. In 1926 Levi proved that a nontrivial arrangement—simple or not—of n pseudolines in the projective plane contains at least n triangles. To show the corresponding result for the Euclidean plane, namely, that a simple arrangement of n pseudolines contains at least n-2 triangles, we had to find a completely different proof. On the other hand a nonsimple arrangement of n pseudolines in the Euclidean plane can have as few as 2n/3 triangles and this bound is best possible. We also discuss the maximal possible number of triangles and some extensions. Received February 12, 1998, and in revised form April 7, 1998.     

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.     

Almost Disjoint Triangles in 3-Space

   Abstract. Two triangles are called almost disjoint if they are either disjoint or their intersection consists of one common vertex. Let f(n) denote the maximum number of pairwise almost disjoint triangles that can be found on some vertex set of n points in 3-space. Here we prove that f(n)=Ω(n ^3/2 ) .     

Eppstein's bound on intersecting triangles revisited

Let S be a set of n points in the plane, and let T be a set of m triangles with vertices in S. Then there exists a point in the plane contained in Ω(m³/(n⁶log²n)) triangles of T. Eppstein [D. Eppstein, Improved bounds for intersecting triangles and halving planes, J. Combin. Theory Ser. A 62 (1993) 176-182] gave a proof of this claim, but there is a problem with his proof. Here we provide a correct proof by slightly modifying Eppstein's argument.     

Convex Dimension of Locally Planar Convex Geometries

We prove that convex geometries of convex dimension n that satisfy two properties satisfied by nondegenerate sets of points in the plane, may have no more than 2 ^n-1 points. We give examples of such convex geometries that have n \choose 4 + n \choose 2 + n \choose 0 points. Received June 7, 1999, and in revised form April 18, 2000. Online publication September 22, 2000.     

Distinct Distances in the Plane

It is shown that every set of n points in the plane has an element from which there are at least cn ^6/7 other elements at distinct distances, where c>0 is a constant. This improves earlier results of Erdős, Moser, Beck, Chung, Szemerédi, Trotter, and Székely. Received November 15, 2000, and in revised form December 13, 2000. Online publication April 6, 2001.     

Isosceles Triangles Determined by a Planar Point Set

 It is proved that, for any ɛ>0 and n>n ₀(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos. Received: February, 2002 Final version received: September 15, 2002 RID="*" ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452 RID="†" ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21     

On the number of halving planes

LetS ³ be ann-set in general position. A plane containing three of the points is called a halving plane if it dissectsS into two parts of equal cardinality. It is proved that the number of halving planes is at mostO(n ^2.998).As a main tool, for every setY ofn points in the plane a setN of sizeO(n ⁴) is constructed such that the points ofN are distributed almost evenly in the triangles determined byY.Research supported partly by the Hungarian National Foundation for Scientific Research grant No. 1812     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Ramsey-Type Results for Geometric Graphs, II

We show that for any two-coloring of the segments determined by n points in the plane, one of the color classes contains noncrossing cycles of lengths . This result is tight up to a multiplicative constant. Under the same assumptions, we also prove that there is a noncrossing path of length Ω(n ^2/3 ) , all of whose edges are of the same color. In the special case when the n points are in convex position, we find longer monochromatic noncrossing paths, of length . This bound cannot be improved. We also discuss some related problems and generalizations. In particular, we give sharp estimates for the largest number of disjoint monochromatic triangles that can always be selected from our segments. Received March 25, 1997, and in revised form March 5, 1998.     

The maximum number of odd integral distances between points in the plane

Four points in the plane with pairwise odd integral distances do not exist. The maximum number of odd distances betweenn points in the plane is proved to ben ²/3+r(r-3)/6 for alln, wherer=1,2,3 andn≡r (mod 3). This solves a recently stated problem of Erdós. Dedicated to Professor Dr. H.-J. Kanold on the occasion of his eightieth birthday     

The number of triangles covering the center of an n-set

Let the points P ₁, P ₂, ..., P _nbe given in the plane such that there are no three on a line. Then there exists a point of the plane which is contained in at least n ³/27 (open) P _iP_jP_ktriangles. This bound is the best possible.