Narrow Results

It is proved that every planar surface NEC group Γ admits a fundamental region, called a normal region, which is a hyperbolic right-angled polygon with several pairs of identified sides according to a pattern. Conversely, each such a polygon can be taken as a fundamental region of a planar surface NEC group. By means of these regions the Teichmüller space of Γ is studied, obtaining a parametrization by means of congruence classes of marked polygons. The parameters are certain lengths in these polygons, and from them explicit matrices of the generators of the associated group are obtained.

The study of network models is one of the most challenging research fields among the studies of complex networks, which have been the hot research topics in recent decades. In this paper, we construct a deterministic network by a mapping method based on a recursive graph, and analyze its topological characteristics, including degree distribution, clustering coefficient, network diameter, average path length and degree correlations. We obtain that this network has the small-world property and positive correlation. The network modeling as we present gives a new perspective on networks, and helps to understand better the evolutions of the real-life systems, making it possible to explore the complexity of complex systems.

A family of maps with memory, parameterized by $\alpha$, is shown to have either periodic trajectories or dense trajectories on ellipses which support absolutely continuous invariant measures. Furthermore, for $0<\alpha <\frac{1}{2}$, i.e. $\alpha =\frac{2cos𝜃}{2cos𝜃-1}$ with $𝜃=r(2\pi )$ and $\frac{1}{4}<r<\frac{1}{3}$, all points except $(0,0)$ either go into a polygonal region centered at $(\frac{1}{2-\alpha },\frac{1}{2-\alpha })$ if $r$ is rational, or are attracted to an elliptical region having the same center, if $r$ is irrational. In the polygonal case, we examine a mechanism for the appearance of islands supporting absolutely continuous invariant measures.

A simple polyhedron is weakly-monotonic in direction provided that the intersection of the polyhedron and any plane with normal is simply-connected (i.e. empty, a point, a line-segment or a simple polygon). Furthermore, if the intersection is a convex set, then the polyhedron is said to be weakly-monotonic in the convex sense. Toussaint¹⁰ introduced these types of polyhedra as generalizations of the 2-dimensional notion of monotonicity. We study the following recognition problems:

Given a simple n-vertex polyhedron in 3-dimensions, we present an O(n log n) time algorithm to determine if there exists a direction such that when sweeping over the polyhedron with a plane in direction , the cross-section (or intersection) is a convex set. If we allow multiple convex polygons in the cross-section as opposed to a single convex polygon, then we provide a linear-time recognition algorithm. For simply-connected cross-sections (i.e. the cross-section is empty, a point, a line-segment or a simple polygon), we derive an O(n²) time recognition algorithm to determine if a direction exists.

We then study variations of monotonicity in 2-dimensions, i.e. for simple polygons. Given a simple n-vertex polygon P, we can determine whether or not a line ℓ can be swept over P in a continuous manner but with varying direction, such that any position of ℓ intersects P in at most two edges. We study two variants of the problem: one where the line is allowed to sweep over a portion of the polygon multiple times and one where it can sweep any portion of the polygon only once. Although the latter problem is slightly more complicated than the former since the line movements are restricted, our solutions to both problems run in O(n²) time.

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon by a polygon such that (1) contains , (2) has its reflex vertices at the same positions as , and (3) the number of vertices of is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both and , our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of . We describe several of these applications (including linear-time post-processing steps that might be necessary).

A diagonal guard is a guard capable of moving along an edge or an internal diagonal in a polygon. A polygon which can be guarded by a diagonal guard is called diagonal-visible. We consider the following three problems concerning the diagonal visibility in a polygon P. First, determine whether or not a guard diagonal exists in P, i.e., P is diagonal-visible. Second, compute all guard diagonals of P. Third, given a query diagonal, determine whether or not it is a guard diagonal. For these problems, we construct a data structure for keeping all guard diagonals in O(n log n) time and O(n) space. Using this data structure, we show that these problems can be solved in O(n log n), O(n log n+k), and O(1) time, respectively, where k is the number of guard diagonals.

A simple polygon P is said to be weakly extrenally visible from a line segment L if it lies outside P and for every point p on the boundary of P there is a point q on L such that no point in the interior of lies inside P. In this paper, a linear time algorithm is proposed for computing a shortest line segment from which P is weakly externally visible. This is done by a suitable generalization of a linear time algorithm which solves the same problem for a convex polygon.

Dyadic rationals are rationals whose denominator is a power of 2. Dyadic triangles and dyadic polygons are, respectively, defined as the intersections with the dyadic plane of a triangle or polygon in the real plane whose vertices lie in the dyadic plane. The one-dimensional analogs are dyadic intervals. Algebraically, dyadic polygons carry the structure of a commutative, entropic and idempotent algebra under the binary operation of arithmetic mean. In this paper, dyadic intervals and triangles are classified to within affine or algebraic isomorphism, and dyadic polygons are shown to be finitely generated as algebras. The auxiliary results include a form of Pythagoras' theorem for dyadic affine geometry.

We indicate how certain invariants can be computed for polygonal knots with few edges. This leads to conclusions regarding the minimal number of edges required to represent certain knots.

We define a scale-invariant energy function for polygonal knots in ℜ³ based on the minimum distances between segments. The energy is bounded below by 2π. (minimum crossing number of the knot type). For each knot type, there exists an ideal number of segments, from which can be made an ideal conformation of the knot having minimum energy among all polygons realizing that knot type. Results leading to this include the following: The energy of an n-segment polygon is greater than n; if energy is bounded then ratios of edge lengths and angles are bounded away from zero; changing knot type requires passing an infinite energy barrier. We implement an algorithm, with the feature that preserving knot-type is guaranteed, to discover local energy-minimizing conformations for a given number of segments, and present some of these examples.

This paper applies reverse engineering on the Bresenham's line drawing algorithm [J. E. Bresenham, IBM System Journal, 4, 106–111 (1965)] for polygonal approximation of digital curve. The proposed method has a number of features, namely, it is sequential and runs in linear time, produces symmetric approximation from symmetric digital curve, is an automatic algorithm and the approximating polygon has the least non-zero approximation error as compared to other algorithms.

The extension complexity of a polytope measures its amenability to succinct representations via lifts. There are several versions of extension complexity, including linear, real semidefinite, and complex semidefinite. We focus on the last of these, for which the least is known, and in particular on understanding which polytopes are complex psd-minimal. We prove the existence of an obstruction to complex psd-minimality which is efficiently computable via lattice membership problems. Using this tool, we complete the classification of complex psd-minimal polygons (geometrically as well as combinatorially). In dimension three we exhibit several new examples of complex psd-minimal polytopes and apply our obstruction to rule out many others.

This paper gives algorithms to dissect a rectangle sequentially into polygons that can be reassembled to a rectangle, which is similar to the initial rectangle, and $n$-similar equilateral triangles or regular hexagons and also pentagons or heptagons or octagons with symmetry.

We prove that.

• there exist polygons through 'p' points of which no three are collinear.

• there exist at least one simple polygon through n ≥ 3 points which are not collinear.

• the number of p-sided polygons out of 'n' points of which no three are collinear is ⁿC_r and discuss about.

• the number of p-sided polygons when one set of collinear points, two-sets of collinear points, …, k sets of collinear points which are disjoint or all or some are connected.

We indicate how certain invariants can be computed for polygonal knots with few edges. This leads to conclusions regarding the minimal number of edges required to represent certain knots.

We define a scale-invariant energy function for polygonal knots in ℜ³ based on the minimum distances between segments. The energy is bounded below by 2π (minimum crossing number of the knot type). For each knot type, there exists an ideal number of segments, from which can be made an ideal conformation of the knot having minimum energy among all polygons realizing that knot type. Results leading to this include the following: The energy of an n-segment polygon is greater than n; if energy is bounded then ratios of edge lengths and angles are bounded away from zero; changing knot type requires passing an infinite energy barrier. We implement an algorithm, with the feature that preserving knot-type is guaranteed, to discover local energy-minimizing conformations for a given number of segments, and present some of these examples.

A strategy for working with incomplete information is called competitive if it solves each problem instance at a cost not exceeding the cost of an optimal solution (with full information available), times a constant. This paper strives to demonstrate why competitive strategies are useful for the design of autonomous robots. They guarantee a good worst-case behaviour, they are easy to implement, and they allow to deal with some problems whose optimal solution would be NP-hard. We survey competitive strategies for the following problems. How to find a door in a long wall, how to find a goal in an unknown environment, how to find a point from which an unknown environment is fully visible, and how to determine a robot's location on a known map from local visibility.