Search

A combinatorial algorithm to locate the Maximum Empty Rectangle (MER) inside a given set L of non-intersecting horizontal and vertical line segments is presented in this paper. The MER is the maximum area rectangle such that no line segment lies in part or in full within the rectangle. The proposed algorithm uses the projection lists and line sweep technique 풪(knlog n), where n is the cardinality of the set L, and k is the maximum number of candidate rectangles for a line segment. Projection list is the projection of the line segments on X and Y axes. [ABSTRACT FROM AUTHOR]

Based on Gurtin–Murdoch surface/interface model and complex potential theory, by constructing a new conformal mapping function, the fracture behavior on n nano-cracks emanating from a n-polygon nano-hole under far-field anti-plane mechanical load, inplane electrical load and magnetic load is studied. The analytical solutions of stress intensity factor, electric displacement intensity factor and magnetic induction intensity factor at the crack tip are given under the boundary conditions of magnetoelectrically semi-permeable. In addition, numerical examples show that when considering the surface effect, the stress field intensity factor, electric displacement intensity factor and magnetic induction intensity factor have obvious size-dependence. The results of this paper show that when the defect size increases to a certain extent, the influence of the surface effect begins to decrease, and finally tends to the results of classical elastic theory. [ABSTRACT FROM AUTHOR]

Wen [Some problems in fractal geometry, in Report in Chinese Conference on Fractal Geometry and Dynamical Systems, 2023] posed the following questions: when a quadrangle is a self-similar set with the open set condition (OSC). It is well known that any convex quadrangle is a self-similar set. For the concave quadrangles, this case is more complicated. Loosely speaking, some concave polygons may be not self-similar. In this paper, we prove two results. First, we give a necessary and sufficient condition such that a concave quadrangle is a self-similar set. Moreover, we also give a necessary condition for a concave quadrangle to be a self-similar set with the OSC. For the convex quadrangle, we investigate the trapezoid. We show under some condition that the trapezoid is a self-similar set with the OSC. In particular, for any trapezoid, if the ratio of the lengths of two bases is rational, then the trapezoid is a self-similar set with the OSC. [ABSTRACT FROM AUTHOR]

In this paper, we prove a new extremal property of the Reuleaux triangle: it maximizes the Cheeger constant among all bodies of (same) constant width. The proof relies on a fine analysis of the optimality conditions satisfied by an optimal Reuleaux polygon together with an explicit upper bound for the inradius of the optimal domain. As a possible perspective, we conjecture that this maximal property of the Reuleaux triangle holds for the first eigenvalue of the p -Laplacian for any p ∈ (1 , + ∞) (this paper covers the case p = 1 whereas the case p = + ∞ was already known). [ABSTRACT FROM AUTHOR]

In this paper, we study the Newton polygon of the L -function of a generalized Kloosterman polynomial with two variables over finite fields. We give the explicit form of the monomial basis of the top dimensional cohomology space of the p -adic complex associated to the L -function. One consequence of this result is a concrete method for computing the Hodge polygon. Using decomposition theorems of Wan, we determine when a generalized Kloosterman polynomial is ordinary and when its Newton polytope is generically ordinary. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We revisit classical Virtual Element approximations on polygonal and polyhedral decompositions. We also recall the treatment proposed for dealing with decompositions into polygons with curved edges. In the second part of the paper, we introduce a couple of new ideas for the construction of Virtual Element Method (VEM)-approximations on domains with curved boundary, both in two and three dimensions. The new approach looks promising, although sound numerical tests should be made to validate the efficiency of the method. [ABSTRACT FROM AUTHOR]

In this paper, we study Vicsek polygons and extended Vicsek networks, which are an extension of Vicsek fractal. Our research indices are some Fermat-type indices, including the Fermat eccentricity and the Fermat eccentric distance sum. Fermat-type indices are novel graph invariants with vast potential in research on structure–activity and quantitative structure–property. By the approach of finite pattern, we solve some integrals to gain their asymptotic formulas on Fermat eccentricity and Fermat eccentric distance sum. [ABSTRACT FROM AUTHOR]

In the polygon scaled boundary finite element method, the modeling of crack can be simplified and the stress intensity factors are extracted from the semi-analytical solution directly. These salient features are applied to develop an efficient method to model the impact test specimens, one of which occurs without crack propagation, the other with crack propagation. The notched bend specimens are discretized by polygon elements with no local refinement around the crack tip. The mass and stiffness matrix of polygon elements are derived based on the SBFEM, and then the elastodynamic equations of the global system are established. The Newmark integration method is applied to obtain the dynamic responses of the specimens. For the case with crack propagation, an efficient local remeshing algorithm is used to track the crack tip and model the crack propagation. The dynamic stress intensity factors are computed directly from the instantaneous displacement field and crack velocity. The numerical results of the two specimens correspond well with the experimental data and other numerical results reported in the literature. The effects of the time step, mesh density and damping coefficient are also investigated. Moreover, the displacement and stress contours are extracted from the dynamic solution, which is helpful for the interpretation of the experimental observations. [ABSTRACT FROM AUTHOR]

In this work, a new structure is used to enhance the nonlinear effect in the cavity, which improves the performance of the 1.3 μ m broadband swept source. The swept source adopts a semiconductor optical amplifier (SOA), a circulator, a coupler, and a tunable filter. In the structure, the light passes through the nonlinear medium (SOA) twice in two opposite directions, which excites the nonlinear effect and increases the performance of the swept source. The tunable filter is based on a polygon rotating mirror and gratings. Traditionally, multiple SOAs are adopted to improve the sweep range and the optical power, which increases the cost and complexity of the swept source. The method proposed in this paper can improve the spectral range and optical power of the swept sources without additional accessories. For the short-cavity swept source, the power increases from 6 mW to 7.7 mW, and the sweep range increases from 98 nm to 120 nm. The broadband swept sources could have wide applications in biomedical imaging, sensor system, measurement and so on. [ABSTRACT FROM AUTHOR]

Given a set S of n points, a weight function w to associate a non-negative weight to each point in S, a positive integer k ≥ 1 , and a real number > 0 , we devise the following algorithms to compute a k-vertex fault-tolerant spanner network G (S , E) for the metric space induced by the weighted points in S: (1). When the points in S are located in a simple polygon, we present an algorithm to compute G with multiplicative stretch 1 0 + , and the number of edges in G (size of G) is O (k n (lg n) 2). (2) When the points in S are located in the free space of a polygonal domain with h number of obstacles, we present an algorithm to compute G with multiplicative stretch 6 + and size O (h k n (lg n) 2). (3) When the points in S are located on a polyhedral terrain, we devise an algorithm to compute G with multiplicative stretch 6 + and size O (k n (lg n) 2). [ABSTRACT FROM AUTHOR]

Whether for optimizing the speed of microprocessors or for sequence analysis in molecular biology — evolutionary algorithms are used in astoundingly many fields. Also, the art was influenced by evolutionary algorithms — with principles of natural evolution works of art that can be created or imitated, whereby initially generated art is put through an iterated process of selection and modification. This paper covers an application in which given images are emulated evolutionary using a finite number of semi-transparent overlapping polygons, which also became known under the name "Evolution of Mona Lisa". In this context, different approaches to solve the problem are tested and presented here. In particular, we want to investigate whether Hill Climbing Algorithm in combination with Delaunay Triangulation and Canny Edge Detector that extracts the initial population directly from the original image performs better than the conventional Hill Climbing and Genetic Algorithm, where the initial population is generated randomly. [ABSTRACT FROM AUTHOR]

Dürer's pentagon is known to the artist Albrecht Dürer, whose work has produced an effect on modern telecommunication. In this paper, we consider directed networks generated by Dürer-type polygons, which is based on an M -sided polygon where M = 4 m and m ≥ 2. This object is quite different from what we previously studied when M is not a multiple of 4. We aim to study some properties of these networks, such as degree distribution, clustering coefficient and average path length. We show that such networks have the scale-free effect, but do not have the small-world effect. It is expected that our results will provide certain theoretical support to further applications in modern telecommunication. [ABSTRACT FROM AUTHOR]

In this paper, the new concept i -isodominism between two graphs is introduced, where i is a positive integer. The i -isodominism is a pair of the graph isomorphism which depends on the smallest i -dominating sets. By this tool, a graph with one vertex, complete graphs, wheels and stars are in the same 1 -isodominism class. Furthermore, some results about the 1 -isodominism classes of paths, cycles and star polygon are presented. [ABSTRACT FROM AUTHOR]

Mosaic diagrams for knots were first introduced in 2008 by Lomanoco and Kauffman for the purpose of building a quantum knot system. Since then, many others have explored the structure of these knot mosaic diagrams, as they are interesting objects of study in their own right. Knot mosaics have been generalized by Garduño to virtual knots, by including an additional tile type to represent virtual crossings. There is another interpretation of virtual knots, however, as knot diagrams on surfaces, which inspires this work. By viewing classical mosaic diagrams as 4 n -gons and gluing edges of these polygons, we obtain knots on surfaces that can be viewed as virtual knots. These virtual mosaics are our present objects of study. In this paper, we provide a set of moves that can be performed on virtual mosaics that preserve knot and link type, we show that any virtual knot or link can be represented as a virtual mosaic, and we provide several computational results related to virtual mosaic numbers for small classical and virtual knots. [ABSTRACT FROM AUTHOR]

The offsetting process that defines straight skeletons of polygons is generalized to arc polygons, i.e., to planar shapes with piecewise circular boundaries. The offsets are obtained by shrinking or expanding the circular arcs on the boundary in a co-circular manner, and tracing the paths of their endpoints. These paths define the associated shape-preserving skeleton, which decomposes the input object into patches. While the skeleton forms a forest of trees, the patches of the decomposition have a radial monotonicity property. Analyzing the events that occur during the offsetting process is non-trivial; the boundary of the offsetting object may get into self-contact and may even splice. This leads us to an event-driven algorithm for offset and skeleton computation. Several examples (both manually created ones and approximations of planar free-form shapes by arc spline curves) are analyzed to study the practical performance of our algorithm. [ABSTRACT FROM AUTHOR]

In this work, merging ideas from compatible discretisations and polyhedral methods, we construct novel fully discrete polynomial de Rham sequences of arbitrary degree on polygons and polyhedra. The spaces and operators that appear in these sequences are directly amenable to computer implementation. Besides proving the exactness, we show that the usual three-dimensional sequence of trimmed Finite Element (FE) spaces forms, through appropriate interpolation operators, a commutative diagram with our sequence, which ensures suitable approximation properties. A discussion on reconstructions of potentials and discrete L 2 -products completes the exposition. [ABSTRACT FROM AUTHOR]

In this paper, the evolving networks are created from a series of Sierpinski-type polygon by applying the encoding method in fractal and symbolic dynamical system. Based on the self-similar structures of our networks, we study the cumulative degree distribution, the clustering coefficient and the standardized average path length. The power-law exponent of the cumulative degree distribution is deduced to be log 2 n and the average clustering coefficients have a uniform lower bound 2 n − 3 3 n . Moreover, we find the asymptotic formula of the average path length of our proposed networks. These results show the scale-free and the small-world effects of these networks. [ABSTRACT FROM AUTHOR]

Since the directional permeability of fractured rock masses is significantly dependent on the geometric properties of fractures, in this work, a numerical study was performed to analyze the relationships between them, in which fracture length follows a fractal distribution. A method to estimate the representative elementary volume (REV) size and directional permeability ( K f) by extracting regular polygon sub-models with different orientation angles ( 𝜃 r) and side lengths ( L n) from an original discrete fracture network (DFN) model was developed. The results show that the fracture number has a power law relationship with the fracture length and the evolution of the exponent agrees well with that reported in previous studies, which confirms the reliability of the proposed fractal length distribution and stochastically generated DFN models. The K f varies significantly due to the influence of random numbers utilized to generate fracture location, orientation and length when L n is small. When L n exceeds some certain values, K f holds a constant value despite of 𝜃 r , in which the model scale is regarded as the REV size and the corresponding area of DFN model is represented by S REV (in 2D). The directional permeability contours for DFN models plotted in the polar coordinate system approximate to circles when the model size is greater than the REV size. The S REV decreases with the increment of fractal dimension of fracture length distribution ( D f). However, the decreasing rate of S REV (79.5%) when D f increases from 1.4 to 1.5 changes more significantly than that (34.8%) when D f increases from 1.5 to 1.6 for regular hexagon sub-models. This indicates that the small non-persistent fractures dominate the preferential flow paths; thereafter, the flow rate distribution becomes more homogeneous when D f exceeds a certain value (i.e. 1.5). A larger D f results in a denser fracture network and a stronger conductivity. [ABSTRACT FROM AUTHOR]

The in-plane vibrations of regular polygonal rings composed of rigid segments joined by torsional springs are studied for the first time. The nonlinear dynamical difference equations are formulated and solved by perturbation about the equilibrium state. As the number of segments increase, the frequencies, if aptly normalized, converge to the classical vibration frequencies of a continuous elastic ring. The vibration mode shapes are illustrated. The tiling of many identical polygons is discussed. Possible applications include the vibrations of space structures and graphene sheets. [ABSTRACT FROM AUTHOR]

Given a convex polygon with n vertices, we study the problem of identifying a triangle with its smallest side as large as possible among all the triangles that can be drawn inside the polygon. We show that at least one of the vertices of such a triangle must coincide with a vertex of the polygon. We also propose an O (n 2) time algorithm to compute such a triangle inside the given convex polygon. [ABSTRACT FROM AUTHOR]

We prove that the knots 1 3 n 5 9 2 and 1 5 n 4 1 , 1 2 7 both have stick number 10. These are the first non-torus prime knots with more than 9 crossings for which the exact stick number is known. [ABSTRACT FROM AUTHOR]

We study the shortest k -violation path problem in a simple polygon. Let P be a simple polygon in ℝ 2 with n vertices and let s , t be a pair of points in P. Let i n t (P) represent the interior of P. Let P ̃ = ℝ 2 \ i n t (P) represent the exterior of P. For an integer k ≥ 0 , the shortest k -violation path problem in P is the problem of computing the shortest path from s to t in P , such that at most k path segments are allowed to be in P ̃. The subpaths of a k -violation path are not allowed to bend in P ̃. For any k , we present a (1 + 2 𝜖) factor approximation algorithm for the problem that runs in O (n 2 σ 2 k log n 2 σ 2 + n 2 σ 2 k) time. Here σ = O (log δ (L r)) and δ , L , r are geometric parameters. [ABSTRACT FROM AUTHOR]

We devise the following dynamic algorithms for both maintaining as well as querying for the visibility and weak visibility polygons amid vertex insertions and deletions to the simple polygon. A fully-dynamic algorithm for maintaining the visibility polygon of a fixed point located interior to the simple polygon amid vertex insertions and deletions to the simple polygon. The time complexity to update the visibility polygon of a point q due to the insertion (resp. deletion) of vertex v to (resp. from) the current simple polygon is expressed in terms of the number of combinatorial changes needed to the visibility polygon of q due to the insertion (resp. deletion) of v. An output-sensitive query algorithm to answer the visibility polygon query corresponding to any point p in ℝ 2 amid vertex insertions and deletions to the simple polygon. If p is not exterior to the current simple polygon, then the visibility polygon of p is computed. Otherwise, our algorithm outputs the visibility polygon corresponding to the exterior visibility of p. An incremental algorithm to maintain the weak visibility polygon of a fixed-line segment located interior to the simple polygon amid vertex insertions to the simple polygon. The time complexity to update the weak visibility polygon of a line segment p q due to the insertion of vertex v to the current simple polygon is expressed in terms of the sum of the number of combinatorial updates needed to the geodesic shortest path trees rooted at p and q due to the insertion of v. An output-sensitive algorithm to compute the weak visibility polygon corresponding to any query line segment located interior to the simple polygon amid both the vertex insertions and deletions to the simple polygon. Each of these algorithms requires preprocessing the initial simple polygon. And, the algorithms that maintain the visibility polygon (resp. weak visibility polygon) compute the visibility polygon (resp. weak visibility polygon) with respect to the initial simple polygon during the preprocessing phase. [ABSTRACT FROM AUTHOR]

In this paper, we consider a restricted covering problem, in which a convex polygon P with n vertices and an integer k are given, the objective is to cover the entire region of P using k congruent disks of minimum radius r o p t , centered on the boundary of P. For k ≥ 7 and any 𝜖 > 0 , we propose an (1 + 7 k + 7 𝜖 k + 𝜖) -factor approximation algorithm for this problem, which runs in O ((n + k) (| log r o p t | + log ⌈ 1 𝜖 ⌉)) time. The best known approximation factor of the algorithm for the problem in the literature is 1.8841 [H. Du and Y. Xu: An approximation algorithm for k -center problem on a convex polygon, J. Comb. Optim. 27(3) (2014) 504–518]. [ABSTRACT FROM AUTHOR]

This work introduces a new sensing system for biped robots based on plantar robot skin, which provides not only the resultant forces applied on the ankles but a precise shape of the pressure distribution in the sole together with other extra sensing modalities (temperature, pre-touch and acceleration). The information provided by the plantar robot skin can be used to compute the center of pressure and the ground reaction forces. This information also enables the online construction of the supporting polygon and its preemptive shape before foot landing using the proximity sensors in the robot skin. Two experiments were designed to show the advantages of this new sensing technology for improving balance and walking controllers for biped robots over unknown terrain. [ABSTRACT FROM AUTHOR]

This paper studies a searching problem in an unknown street. A simple polygon P with two distinguished vertices, s and t , is called a street if the two boundary chains from s to t are mutually weakly visible. We use a mobile robot to locate t starting from s. Assume that the robot has a limited sensing capability that can only detect the constructed edges (also called gaps) on the boundary of its visible region, but cannot measure any angle or distance. The robot does not have knowledge of the street in advance. We present a new competitive strategy for this problem and prove that the length of the path generated by the robot is at most 9-times longer than the shortest path. We also propose a matching lower bound to show that our strategy is optimal. Compared with the previous strategy, we further relaxed the restriction that the robot should take a marking device and use the data structure S-GNT. The analysis of our strategy is tight. [ABSTRACT FROM AUTHOR]

We study a turn-based game in a simply connected polygonal environment Q between a pursuer 𝒫 and an adversarial evader ℰ. Both players can move in a straight line to any point within unit distance during their turn. The pursuer 𝒫 wins by capturing the evader, meaning that their distance satisfies d (𝒫 , ℰ) ≤ 1 , while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader ℰ always knows the location of 𝒫. Meanwhile, 𝒫 only has line-of-sight visibility: 𝒫 observes the evader's position only when the line segment connecting them lies entirely within the polygon. Therefore 𝒫 must search for ℰ when the evader is hidden from view. We provide a winning strategy for 𝒫 in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line L can be moved continuously over Q so that (1) L ∩ Q is a line segment and (2) every point on the boundary ∂ Q is swept exactly once. These are both subfamilies of strictly sweepable polygons. The sweeping motion for a monotone polygon is a single translation, and the sweeping motion for a scallop polygon is a single rotation. Our algorithms use rook's strategy during its pursuit phase, rather than the well-known lion's strategy. The rook's strategy is crucial for obtaining a capture time that is linear in the area of Q. For both monotone and scallop polygons, our algorithm has a capture time of O (n (Q) + area (Q)) , where n (Q) is the number of polygon vertices. [ABSTRACT FROM AUTHOR]

In this paper, we consider the algebra A (Γ ♢) associated to Hasse graph of a star polygon. We determine the automorphism group for this algebra and the graded traces Tr σ (t) for each σ ∈ Aut (A (Γ ♢)) , which are the graded trace generating functions of A (Γ ♢). Furthermore, we study the representations of Aut (A (Γ ♢)) acting on each homogeneous component of A (Γ ♢) and we apply the same technique to the dual algebra A (Γ ♢) ! of gr (A (Γ ♢)). More precisely, we consider the algebras associated to Hasse graph of star polygons { n p } with n ≥ 5 odd. [ABSTRACT FROM AUTHOR]

For a polygon in the d -dimensional Euclidean space, we give two kinds of normalizations of its m th midpoint polygon by a homothetic transformation and an affine transformation, respectively. As m goes to infinity, the normalizations will approach "regular" polygons inscribed in an ellipse and a generalized Lissajous curve, respectively, where the curves may be degenerate. The most interesting case is when d = 3 , where polygons with all its m th midpoint polygons knotted are discovered and discussed. Such polygonal knots can be seen as a discrete version of the Lissajous knots. [ABSTRACT FROM AUTHOR]

We extend results by Biedl et al. (ISVD'13) on the recognition and reconstruction of straight skeletons: Given a geometric tree G , can we recognize whether G resembles a weighted straight skeleton 𝒮 and, if so, can we reconstruct an appropriate polygonal input P and an appropriate positive weight function σ such that 𝒮 (P , σ) = G ? We show that a solution polygon P and a weight function σ can be found in O (n) time and space for a geometric tree G with n faces if at most one node of G has two incident edges that span an angle greater than π. In addition, we show that G implicitly encodes enough information such that all other weighted bisectors of any solution P can be obtained from G without explicitly computing P. [ABSTRACT FROM AUTHOR]

For a positive integer n ≥ 3 , the collection of n -sided polygons embedded in 3 -space defines the space of geometric knots. We will consider the subspace of equilateral knots, consisting of embedded n -sided polygons with unit length edges. Paths in this space determine isotopies of polygons, so path-components correspond to equilateral knot types. When n ≤ 5 , the space of equilateral knots is connected. Therefore, we examine the space of equilateral hexagons. Using techniques from symplectic geometry, we can parametrize the space of equilateral hexagons with a set of measure preserving action-angle coordinates. With this coordinate system, we provide new bounds on the knotting probability of equilateral hexagons. [ABSTRACT FROM AUTHOR]

An integer of the form p m (x) = (m − 2) x 2 − (m − 4) x 2   (m ≥ 3) , for some integer x , is called a generalized polygonal number of order m. A ternary sum Φ i , j , k a , b , c (x , y , z) = a p i + 2 (x) + b p j + 2 (y) + c p k + 2 (z) of generalized polygonal numbers, for some positive integers a , b , c and some integers 1 ≤ i ≤ j ≤ k , is said to be universal over ℤ if for any nonnegative integer n , the equation Φ i , j , k a , b , c (x , y , z) = n has an integer solution x , y , z. In this paper, we prove the universalities of 1 7 ternary sums of generalized polygonal numbers, which was conjectured by Sun. [ABSTRACT FROM AUTHOR]

The objective of this paper is to apply clipping techniques on natural images and to analyze the performance of various clipping algorithms in computer graphics. The clipping techniques used in this paper is Cohen–Sutherland line clipping, Liang–Barsky line clipping, Nicholl–Lee–Nicholl line clipping and Sutherland–Hodgman polygon clipping. The clipping algorithms are evaluated by using the three parameters: time complexity, space complexity and image accuracy. Previously, there is no performance evaluation on clipping algorithms done. Motivating by this factor, in this paper an evaluation of clipping algorithms is made. The novelty of this paper is to apply the clipping algorithms on natural images. It is justified that the above mentioned clipping algorithms outperform well on clipping the natural images. [ABSTRACT FROM AUTHOR]

We relate some terms on the boundary of the Newton polygon of the Alexander polynomial Δ (x , y) of a rational link to the number and length of monochromatic twist sites in a particular diagram that we call the standard form. Normalize Δ (x , y) to be a true polynomial (as opposed to a Laurent polynomial), in such a way that terms of even total degree have positive coefficients and terms of odd total degree have negative coefficients. If the rational link has a reduced alternating diagram with no self-crossings, then Δ (− 1 , 0) = 1. If the standard form of the rational link has M monochromatic twist sites, and the j th monochromatic twist site has m j crossings, then Δ (− 1 , 0) = ∏ j = 1 M (m j + 1). Our proof employs Kauffman's clock moves and a lattice for the terms of Δ (x , y) in which the y -power cannot decrease. [ABSTRACT FROM AUTHOR]

A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q , our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q. [ABSTRACT FROM AUTHOR]

This study deals with the generalized second moment of area (GSMA) of regular polygon cross-sections for the Ludwick type material and its application to cantilever column buckling. In the literature, the GSMA for the Ludwick type material has only been considered for rectangular, elliptical and superellipsoidal cross-sections. This study calculates the GSMAs of regular polygon cross-sections other than those mentioned above. The GSMAs calculated by varying the mechanical constant of the Ludwick type material for the equilateral triangle, square, regular pentagon, regular hexagon and circular cross-sections are reported in tables and figures. The GSMAs obtained from this study are applied to cantilever column buckling, with results shown in tables and figures. [ABSTRACT FROM AUTHOR]

To acquire a stable reverberation signal from an irregular ocean bottom, we derive the analytic surface integral of a scattered signal using Stokes' theorem while approximating the bottom using a combination of polygon facets. In this approach, the delay difference in the elemental scattering area is considered, while the representative delay is used for the elemental scattering area in the standard reverberation model. Two different reverberation models are applied to a randomly generated rough bottom, which is composed of triangular facets. Their results are compared, and the scheme using analytic integration shows a converged reverberation signal, even with a large elemental scattering area, at the cost of an additional computational burden caused by a higher order approximation in the surface integral of the scattered signals. [ABSTRACT FROM AUTHOR]

Piecewise-linear terrains ("roofs") over simple polygons were first studied by Aichholzer et al. (J. UCS 1995) in their work on straight skeletons of polygons. We show how to construct a roof over the polygonal footprint of a building that has minimum or maximum volume among all roofs that drain water. Our algorithm for computing such a roof extends the standard plane-sweep approach known from the theory of straight skeletons by additional events. For both types of roofs our algorithm runs in 𝒪 (n 3 log n) time for a simple polygon with n vertices. [ABSTRACT FROM AUTHOR]

In this paper, continuous piecewise quadratic finite element wavelets are constructed on general polygons in . The wavelets are stable in for and have two vanishing moments. Each wavelet is a linear combination of 11 or 13 nodal basis functions. Numerically computed condition numbers for are provided for the unit square. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of almost squares and extend the result of the author’s fourth paper in the series to almost squares with closer factors. We prove that almost all intervals [x,x+3x1/2−𝜃log2+𝜖x] contain a (𝜃,C)-almost square for any 1/4≤𝜃≤1/2 and C>0. [ABSTRACT FROM AUTHOR]

We address the problem of reconstructing a polygon from the multiset of its edges. Given n line segments in the plane, find a polygon with n vertices whose edges are these segments, or report that none exists. It is easy to solve the problem in O(nlogn) time if we seek an arbitrary polygon or a simple polygon. We show that the problem is NP-complete for weakly simple polygons, that is, a polygon whose vertices can be perturbed by at most 𝜀, for any 𝜀>0, to obtain a simple polygon. We give O(n)-time algorithms for reconstructing weakly simple polygons: when all segments are collinear or the segment endpoints are in general position. These results extend to the variant in which the segments are directed. We study related problems for the case that the union of the n input segments is connected. (i) If each segment can be subdivided into several segments, find the minimum number of subdivision points to form a weakly simple polygon. (ii) If new line segments can be added, find the minimum total length of new segments that creates a weakly simple polygon. We give worst-case upper and lower bounds for both problems. [ABSTRACT FROM AUTHOR]

Given a set S of n points in the plane, how many universal guards are sometimes necessary and always sufficient to guard any simple polygon with vertex set S? We call this problem a Universal Guard Problem and provide a spectrum of results. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities. [ABSTRACT FROM AUTHOR]

A -workspace algorithm may use a workspace of words which can be read and written, in addition to their input, which is provided as a read-only array of items. We present a -workspace algorithm for constructing the shortest path tree of a simple polygon with vertices, with respect to a given point inside the polygon in time, where is the time for computing the visibility polygon of a given point inside a simple polygon with additional words of space. [ABSTRACT FROM AUTHOR]

A quadrisecant line of a knot K is a straight line which intersects K in four points, and a quadrisecant is a 4-tuple of points of K which lie in order along the quadrisecant line. If K has a finite number of quadrisecants, take W to be the set of points of K which are in a quadrisecant. Replace each subarc of K between two adjacent points of W along K with the straight line segment between them. This gives the quadrisecant approximation of K. It was conjectured that the quadrisecant approximation is always a knot with the same knot type as the original knot. We show that every knot type contains two knots, the quadrisecant approximation of one knot has self-intersections while the quadrisecant approximation of the other knot is a knot with a different knot type. [ABSTRACT FROM AUTHOR]

Looking for a handy and exact calculation for the equivalent resistance of an M× N resistor network is important, but difficult. In this paper, we present a standard and convenient approach to calculate the equivalent resistance of an M× N cobweb resistor network by applying multiple external current sources based on the nodal analysis in circuit theory and the recursion-transform (R-T) method. The test current source acts on different nodes in radial direction to obtain an analytical expression for the equivalent resistance between nodes of an M× N cobweb resistor network in radial direction. In our scheme, recalculations are not required to obtain the equivalent resistance between different radial nodes. We also discuss the influence of polygon sides of cobweb network and the ratio between two unit resistances on the equivalent resistance. The results show that, when the number of similar polygons M is given, with the increasing of the polygon sides and the ratio between two unit resistance, the equivalent resistances between two arbitrary radial nodes tend to a constant. [ABSTRACT FROM AUTHOR]

Four geometric conditions on a geodesic metric space, which are stronger variants of classical conditions characterizing hyperbolicity (featuring -thin polygons, the Gromov product or the mesh of triangles), are proved to be equivalent. They define the class of polygon hyperbolic geodesic metric spaces. In the particular case of the Cayley graph of a finitely generated group, it is shown that they characterize virtually free groups. [ABSTRACT FROM AUTHOR]