Problems On Planar Finite Point Sets In Combinatorial Geometry

Let P be a finite planar point set with no three collinear. An interior point of P is a point of P that is not on the boundary of the convex hull CH(P) of P. Let I(P) denote the set consisting of all interior points of P, V(P) = P\I(P) the set of vertices of P.For any integer k≥1, let g(k) be the smallest integer such that every finite planar point set P with no three collinear containing at least g(k) interior points has a subset Q (?) P whose convex hull's interior intCH(Q) contains exactly k interior points of P. More explicitly,g(k) =: min{s : |I(P)|≥s(?)(?)Q(?)P, |I(P)∩intCH(Q)| = k}.In 2001 Avis et al. showed that g(1) = 1,0(2) = 4, g(3)≥8 and g(k)≥k + 2 for k≥4. In 2003 Fevens showed that g(k)≥3k - 1 for k≥3.The existence or finiteness of g(k) for any nonnegative integer k is still an open problem. Letg_â–³(k) =: min{s : |V(P)| = 3, |I(P)|≥s(?)(?)Q(?)P,|I(P)∩intCH(Q)| = k}.In 2004 Bisztriczky et al. proved that for every nonnegative integer k, if gâ–³(k) is finite, then g(k) is also finite.In this dissertation the important result g(3) = 9 is obtained, and the lower bound of g(3) is improved to g(k)≥3k for k≥3.Another important research problem about interior points is to determineh(k) =: min{s : |I(P)|≥s(?)(?)Q(?)P,|I(P)∩intCH(Q)| = k or k + 1},where P is any finite planar point set with no three collinear. Avis et al. proved h(4) = 7 in 2000. Fevens proved in 2003 that h(k)≥2k + 1 for 5≤k≤8; and h(k)≥3k - 7 for k > 8. This dissertation proves that h(5) = 11.According to Branko Grunbaum and G. C. Shaphard, a plane tiling T is a countablefamily of closed sets T = {T_,T₂,…} such that the union of the sets T₁,T₂,…is to be the whole plane, and the interiors of the sets T_i are to be pairwise disjoint. Here T₁,T₂,…are known as the tiles of T. The intersection of any finite set of tiles of T containing at least two distinct tiles may be empty or may consist of a set of isolated points and straight line segments. The points of intersection are called vertices of the tiling and the segments of intersection are called edges of the tiling. An edge-to-edge tiling is a type of tiling where each tile is a polygon and adjacent tiles only share full sides. A vertex around which, in cyclic order, we have an n₁ -gon, an n₂-gon, etc., is said to be of type [n₁.n₂.…]. There exist precisely 11 distinct edge-to-edge tilings by regularpolygons such that all vertices are of the same type. These 11 tilings are called theArchimedean Tilings. The Archimedean tiling with vertices of type [n₁.n₂.…….n_r]is called [n₁.n₂.…….n_r]-tiling.Let H be the set of vertices of a [6.6.6]-tiling, that is, a tiling of the plane by regular hexagons with unit edge. A point of H is called an H-point, a simple polygon in R² whose comers lie in H is called an H-polygon. Reay and Ding initiated the research work in 1987 about the enumeration problems of H-gons with some problems solved. In recent years Kolodziejczyk obtained a series of profound results about the related problems, and suggested a conjecture b(P)≤3i(P) + 7 about b(P) the number of boundary H points of a H-polygon P and i(P) the number of interior points of P. In 2004 Kotodziejczyk proved that for an H-triangleâ–³with exactly one interior H-point, 6(â–³)∈{3, 4, 5, 6, 7, 8, 10}.This dissertation extends the result by showing that any H-triangle with exactlyk interior H-points can have at most 3k+ 7 H-points on its boundary. Moreovertwo conjectures about H-polygons are posed.A finite planar set P is called k-isosceles for k≥3, if every k-point subset of P contains three points with one of them equidistant from the other two. In 1998 Fishburn discussed 3-isosceles sets and 4-isosceles sets, provided all possible configurations of 3-isosceles sets and some partial results about 4-isosceles sets, and put forward 6 open questions about 4-isosceles sets. In 2002 Xu and Ding gave affirmative answers to four of them and provided complete results.This dissertation discusses further three of Fishburn's problems, provides a new 4-isosceles 7-point set with no four points on a circle and no three points on a line, and characterizes some special convex 4-isosceles 7-point sets.