Largest bounding box,smallest diameter,and related problems on imprecise points

Imprecision of input data is one of the main obstacles that prevent geometric algorithms from being used in practice. We model an imprecise point by a region in which the point must lie. Given a set of imprecise points, we study computing the largest and smallest possible values of various basic geometric measures on point sets, such as the diameter, width, closest pair, smallest enclosing circle, and smallest enclosing bounding box. We give efficient algorithms for most of these problems, and identify the hardness of others.     

On 5-isosceles sets in the plane, with linear restriction

A finite planar set is k-isosceles for k≥3 if every k-point subset of the set contains a point equidistant from two others. We show that an 8-set on a line is 5-isosceles if and only if its adjacent interpoint distances are equal to each other, and no 5-isosceles 9-set has 9 points on a line. We also show that the maximum 5-isosceles set with 8 points on a line contains at most 10 points.     

Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the set?s chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

Reprint of: Extreme point and halving edge search in abstract order types

Many properties of finite point sets only depend on the relative position of the points, e.g., on the order type of the set. However, many fundamental algorithms in computational geometry rely on coordinate representations. This includes the straightforward algorithms for finding a halving line for a given planar point set, as well as finding a point on the convex hull, both in linear time. In his monograph Axioms and Hulls, Knuth asks whether these problems can be solved in linear time in a more abstract setting, given only the orientation of each point triple, i.e., the setʼs chirotope, as a source of information. We answer this question in the affirmative. More precisely, we can find a halving line through any given point, as well as the vertices of the convex hull edges that are intersected by the supporting line of any two given points of the set in linear time. We first give a proof for sets realizable in the Euclidean plane and then extend the result to non-realizable abstract order types.     

Locating and counting bifurcation points of satellite components from the main component in the degree-n bifurcation set

The bifurcation point where a satellite component buds from another component is characterized by the existence of the common tangent line between the two osculating components appearing in the degree-n bifurcation set. We investigate the existence, location and number of bifurcation points for satellite components budding from the main component in the degree-n bifurcation set as well as a parametric boundary equation of the main component of the degree-n bifurcation set. Cusp points are also located on the boundary of the main component. Typical degree-n bifurcation sets and their components are illustrated with some computational results.     

Transitive bislim geometries of gonality 3, Part II: The group theoretic cases

We consider point-line geometries having three points on every line, having three lines through every point (bislim geometries), and containing triangles. We classify such geometries under the hypothesis of the existence of a collineation group acting transitively on the point set.     

Empty region graphs

A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This way of defining graphs is not new, and ERGs include several known proximity graphs such as Nearest Neighbor Graphs, β-Skeletons or Θ-Graphs. The main contribution is to provide insight and connections between the definition of ERG and the properties of the corresponding graphs.We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set.     

Two point sets with additional properties

A subset of the plane is called a two point set if it intersects any line in exactly two points. We give constructions of two point sets possessing some additional properties. Among these properties we consider: being a Hamel base, belonging to some σ-ideal, being (completely) nonmeasurable with respect to different σ-ideals, being a κ-covering. We also give examples of properties that are not satisfied by any two point set: being Luzin, Sierpiński and Bernstein set. We also consider natural generalizations of two point sets, namely: partial two point sets and n point sets for n = 3, 4, …, ?₀, ?₁. We obtain consistent results connecting partial two point sets and some combinatorial properties (e.g. being an m.a.d. family).     

Cone Fields and Topological Sampling in Manifolds with Bounded Curvature

A standard reconstruction problem is how to discover a compact set from a noisy point cloud that approximates it. A finite point cloud is a compact set. This paper proves a reconstruction theorem which gives a sufficient condition, as a bound on the Hausdorff distance between two compact sets, for when certain offsets of these two sets are homotopic in terms of the absence of μ-critical points in an annular region. We reduce the problem of reconstructing a subset from a point cloud to the existence of a deformation retraction from the offset of the subset to the subset itself. The ambient space can be any Riemannian manifold but we focus on ambient manifolds which have nowhere negative curvature (this includes Euclidean space). We get an improvement on previous bounds for the case where the ambient space is Euclidean whenever μ≤0.945 (μ∈(0,1) by definition). In the process, we prove stability theorems for μ-critical points when the ambient space is a manifold.     

Gate points in continuous location between regions with different ?p norms

In this paper, a set of notable points is given from the ?_p-distance between a point P and a straight line r. The problem of the geodesic path between two points of R² separated by a straight line r with different norms in each half-plane is then studied from the notable points of these points. This geodesic path provides a point in r, called the “Gate point”, which is studied by varying ?_p- and ?_q-distances, and the slope m of the straight line r. The analytical expression of the Gate point is given in some particular cases.     

On the existence of a point subset with three or five interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let h(k) be the smallest integer such that every point set in the plane, no three collinear, with at least h(k) interior points, has a subset with k or k + 2 interior points of P. We prove that h(3) = 8.     

Centers and shore points of a dendroid

A bottleneck in a dendroid is a continuum that intersects every arc connecting two nonempty open sets. Every dendroid contains a point called a center which is contained in arbitrarily small bottlenecks. A subset A of a dendroid is a shore set if for every ε>0 there is a continuum in D?A with Hausdorff distance from D less than ε. If a shore set has only one point it is called a shore point. This paper explores the relationship between center points and shore points in a dendroid. We show that if a dendroid contains a strong center, then any finite union of the arc components of the set of shore points is a shore set.     

Near-pole polar diagram of objects and duality

The polar diagram of a set of points in a plane and its extracted dual EDPD were recently introduced for static and dynamic cases. In this paper, the near-pole polar diagram NPPD for a set of points is presented. This new diagram can be considered as a generalization of the polar diagram and has applications in several communication systems and robotics problems. After reviewing the NPPD of points, we solve the problem for a set of line segments and simple polygons in optimal time Θ(n log n), where n is the number of line segments or polygon vertices. We introduce duality for the NPPD of points and identify some applications.     

Witness Rectangle Graphs

In a witness rectangle graph (WRG) on vertex point set P with respect to witness point set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally, we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n points.     

A minimum blocking semioval in PG(2, 9)

A blocking semioval is a set of points in a projective plane that is both a blocking set (i.e., every line meets the set, but the set contains no line) and a semioval (i.e., there is a unique tangent line at each point). The minimum size of a blocking semioval is currently known in all projective planes of order < 11, with the exception of PG(2, 9). In this note we show by demonstration of an example that the smallest blocking semioval in PG(2, 9) has size 21 and investigate some properties of this set.     

A Note on the Value in the Disjoint Convex Partition Problem

Let P be a planar point set with no three points collinear; k points of P form a k-hole of P if these k points are the vertices of a convex polygon whose interior contains no points of P. Inthis article, we prove that any planar point set containing at least 13 points with no three points collinear contains pairwise disjoint 3-, 4-, and 5-holes if there exists a separating line SL₄.     

More on planar point subsets with a specified number of interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let g(k) be the smallest integer such that every set P of points in the plane with no three collinear points and with at least g(k) interior points has a subset containing precisely k interior point of P. We prove that g(k) ≥ 3k for k ≥ 3, which improves the known result that g(k) ≥ 3k ? 1 for k ≥ 3.     

A self-correcting point process

Suppose a point process is attempting to operate as closely as possible to a deterministic rate ρ, in the sense of aiming to produce ρt points during the interval (0,t] for all t. This can be modelled by making the instantaneous rate of t of the process a suitable function of n-ρt, n being the number of points in [0, t]. This paper studies such a self-correcting point process in two cases: when the point process is Markovian and the rate function is very general, and when the point process is arbitrary and the rate function is exponential. In each case it is shown that as t→∞ the mean number of points occuring in (0, t] is ρt+O(1) while the variance is bounded further, in the Markov case all the absolute central moments are bounded. An application to the outputs of stationary D/M/s queues is given.     

Spectral analysis and exponential stability of one-dimensional wave equation with viscoelastic damping

This paper presents the exponential stability of a one-dimensional wave equation with viscoelastic damping. Using the asymptotic analysis technique, we prove that the spectrum of the system operator consists of two parts: the point and continuous spectrum. The continuous spectrum is a set of N points which are the limits of the eigenvalues of the system, and the point spectrum is a set of three classes of eigenvalues: one is a subset of N isolated simple points, the second is approaching to a vertical line which parallels to the imagine axis, and the third class is distributed around the continuous spectrum. Moreover, the Riesz basis property of the generalized eigenfunctions of the system is verified. Consequently, the spectrum-determined growth condition holds true and the exponential stability of the system is then established.     

Attractors and recurrence for dendrite-critical polynomials

We call a rational map f dendrite-critical if all its recurrent critical points either belong to an invariant dendrite D or have minimal limit sets. We prove that if f is a dendrite-critical polynomial, then for any conformal measure μ either for almost every point its limit set coincides with the Julia set of f, or for almost every point its limit set coincides with the limit set of a critical point c of f. Moreover, if μ is non-atomic, then c can be chosen to be recurrent. A corollary is that for a dendrite-critical polynomial and a non-atomic conformal measure the limit set of almost every point contains a critical point.