Search

Kovaleva and Spieksma (SIAM J Discrete Math 20(3):48–768, 2006) considered the problem of stabbing a given set of horizontal line segments with the smallest number of horizontal and vertical lines. The standard LP relaxation for this problem is easily shown to have an integrality gap of at most 2 by treating the horizontal and vertical lines separately. However, Kovaleva and Spieksma observed that threshold rounding can be used to obtain an integrality gap of e / (e - 1) ≈ 1.58 which is also shown to be tight. This is one of the rare known examples where the obvious upper bound of 2 on the integrality gap of the standard LP relaxation can be improved. Our goal in this paper is to extend their proof to two other problems where the goal is to stab a set R of objects with horizontal and vertical lines: in the first problem R is a set of horizontal and vertical line segments, and in the second problem R is a set of unit sized squares. The proof of Kovaleva and Spieksma essentially shows the existence of an appropriate threshold which yields the improved approximation factor. We begin by showing that a random threshold picked from an appropriate distribution works. This reduces the problem to finding an appropriate distribution for a desired approximation ratio. In the first problem, we show that the required distribution can be found by solving a linear program. In the second problem, while it seems harder to find the optimal distribution, we show that using the uniform distribution an improved approximation factor can still be obtained by solving a number of linear programs. [ABSTRACT FROM AUTHOR]

The 1971 Fortuin–Kasteleyn–Ginibre inequality for two monotone functions on a distributive lattice is well known and has seen many applications in statistical mechanics and other fields of mathematics. In 2008, one of us (Sahi) conjectured an extended version of this inequality for all n > 2 monotone functions on a distributive lattice. Here, we prove the conjecture for two special cases: for monotone functions on the unit square in R k whose upper level sets are k-dimensional rectangles and, more significantly, for arbitrary monotone functions on the unit square in R 2 . The general case for R k , k > 2 , remains open. [ABSTRACT FROM AUTHOR]

Problems are the intellectual product of mathematics competitions. Many of these problems lead to interesting generalizations. Sometimes the generalizations are beyond elementary mathematics and they are real challenges for professional mathematicians. Such generalizations are a basis of some of the discoveries in mathematics. This paper presents the development of ideas, inspired by problems from mathematics competitions, as beautiful mathematical discoveries. The problems are about the partitions of a polygon (mainly a rectangle) into different shapes – a topic that is fruitful for both creation of problems for mathematics competitions and for mathematical discoveries. [ABSTRACT FROM AUTHOR]

The Boolean rank of a 0,1-matrix A, denoted Rb(A), is the smallest number of monochromatic combinatorial rectangles needed to cover the 1-entries of A. In 1988, de Caen, Gregory, and Pullman asked if the Boolean rank of the Kronecker product C n ® C n is strictly smaller than the square of RB(C n), where C n is the n x n matrix with zeros on the diagonal and ones everywhere else (Carib. Conf. Comb. & Comp., 1988). A positive answer was given by Watts for n = 4 (Linear Alg. and its Appl., 2001). A result of Karchmer, Kushilevitz, and Nisan, motivated by direct-sum questions in non-deterministic communication complexity, implies that the Boolean rank of C n ® C n grows linearly in that of C n (SIAM J. Disc. Math., 1995), and thus Rb(C n ® C n) < RB(C n)2 for every sufficiently large n. Their proof relies on a probabilistic argument. In this work, we present a general method for proving upper bounds on the Boolean rank of Kronecker products of 0,1-matrices. We use it to affirmatively settle the question of de Caen et al. for all integers n > 7. We further provide an explicit construction of a cover of C n ® C n , whose number of rectangles nearly matches the optimal asymptotic bound. Our method for proving upper bounds on the Boolean rank of Kronecker products might find applications in different settings as well. We express its potential applicability by extending it to the wider framework of spanoids, recently introduced by Dvir, Gopi, Gu, and Wigderson (SIAM J. Comput., 2020). [ABSTRACT FROM AUTHOR]

A bicolored rectangular family BRF is the collection of all axis-parallel rectangles formed by selecting a bottom-left corner from a finite set of points A and an upper-right corner from a finite set of points B. We devise a combinatorial algorithm to compute the maximum independent set and the minimum hitting set of a BRF that runs in O (n 2.5 log n) -time, where n = | A | + | B | . This result significantly reduces the gap between the Ω (n 7) -time algorithm by Benczúr (Discrete Appl Math 129 (2–3):233–262, 2003) for the more general problem of finding directed covers of pairs of sets, and the O (n 2) -time algorithms of Franzblau and Kleitman (Inf Control 63(3):164–189, 1984) and Knuth (ACM J Exp Algorithm 1:1, 1996) for BRFs where the points of A lie on an anti-diagonal line. Furthermore, when the bicolored rectangular family is weighted, we show that the problem of finding the maximum weight of an independent set is NP -hard, and provide efficient algorithms to solve it on important subclasses. [ABSTRACT FROM AUTHOR]

Introduction This paper presents an algorithm for covering orthogonal polygons with minimal number of guards. This idea examines the minimum number of guards for orthogonal simple polygons (without holes) for all scenarios and can also find a rectangular area for each guards. We consider the problem of covering orthogonal polygons with a minimum number of r-stars. In each orthogonal polygon P, two points' p and q are called r-visible if these two points are in opposite rectangular corners, then the entire rectangle is placed in P. Now we consider a polygon P to be an r-Star if there is a point p in it so that every point q is r-visible from p. In this paper, we propose an algorithm that applies to all simple orthogonal polygons and is able to locate at least the number of guards. Using a method called a rectangular (orthogonal polygonal division into a number of rectangles), the algorithm separates a number of r-stars and processes them in order to insert guards in their place to reach the target, which has the minimum number of guards. Our proposed algorithm is able to determine the minimum number of guards with a rectangular shape at time O (n5) while the execution order of the best available algorithms is O (n17 poly-logn). Another advantage of this algorithm is the independence of restrictions on simple orthogonal polygons. Material and methods Our processing is based on orthogonal or right-angled polygons, so we only have four types of edges. The northern edge, or N, the southern edge or S, the eastern edge or E, the western edge or W-edge. If the interior of polygon lies below/above/left/right of an edge, respectively, then that edge is called N/S/E/W, respectively. There are also four types of dents, including North Dent (N-dent), Southern Dent (S-dent), Eastern Dent (E-dent) and Western Dent (W-dent); see Figure 1. Figure 1. A simple orthogonal polygon with a variety of edges and dents In our proposed algorithm, after rectangles, new edges and vertices are created in the orthogonal polygon P, which we call the sub-edges and sub-vertices. Sub-vertices are known as horizontal and vertical edges, and are formed from the intersection of the adjacent edges with the main or minor edges. The orthogonal polygons can be classified into class-k, such that 1≤k≤4, according to the type of dents which is defined so that its intersections are at most k different directions. Class-2 polygons can be re-categorized into classes 2a, so that 2 directions are parallel to the dents (i.e., N and S or E and W) and Class 2b so that 2 directions are perpendicular to each other. The field of view of the guards or a rectangular field of view is defined as r-visibility. In each orthogonal polygon P, two opposite-corner situated points p and q are called r-visible to each other if the entire rectangle containing them is within P. Now we consider P to be an r-Star if there is a point p in it so that every point q is r-visible from p. In the r-Star problem, we assume that each guard has a 360-degree field of view. Results and discussion In this paper, a new idea is proposed based on the rectangular orthogonal polygon, which creates new edges. In fact, the original orthogonal polygon P with a rectangular method will be divided into a number of rectangles, so that their geometric communities are exactly the same as P. Then the edges are placed in the two groups of main and minor edges. Obviously, the shared edges between the two rectangles are minor and will not prevent the guard from seeing. Therefore, the primary polygon is decomposed into rectangles and then, according to the orthogonal polygon partition method, P is divided into two or more orthogonal polygons, if possible. We make each one of them an r-Star. Then set the deadlock rectangles and set up an incremental guard in each range for each of them. In the next step, we start from the top r-Star with a sweep-line method and check the inserted guards and, if necessary, r-stars and guard rectangles are requested by our Rectangular Guards method. We will continue to work and expand the first r-Star as far as possible, and will do so for the rest of the r-stars, so that the minimum number of guards or let's say the least number of r-stars are obtained. In this article, we are actually looking for the minimum number of r-stars. The steps of our novel algorithm are as follows: 1. Partitioning into rectangles 2. Partitioning the output of Step 1 into orthogonal r-Stars. 3. Determining the guards for the output of Step 2. 4. Scrolling among the r-stars and setting the minimum number of guards 5. Allocating guards for parent, child and minor r-Stars. Conclusion We considered the problem of covering simple orthogonal polygons with no restrictions on the type and number of dents. This algorithm is capable of Partitioning into smaller rectangles, each of which is an r-star polygon. Updating the range of rectangular guards into the registered guards (in order of their priority). Reaching the minimum number of guards. In this paper, the idea was presented on simple orthogonal polygons that do not have a hole. This paper also paves the way for working on other types of polygons that have cavities. In fact, holes can be seen as columns in the gallery, which can also be considered as simple orthogonal rectangles or polygons. The problem here is that these rectangles are different with the rectangles in the polygon that are presented in this article and prevent the guards from seeing../files/site1/files/42/1Abstract.pdf

We propose the χ-index as a bibliometric indicator that generalises the h-index. While the h-index is determined by the maximum square that fits under the citation curve of an author when plotting the number of citations in decreasing order, the χ-index is determined by the maximum area rectangle that fits under the curve. The height of the maximum rectangle is the number of citations ck to the kth most-cited publication, where k is the width of the rectangle. The χ-index is then defined as , for convenience of comparison with the h-index and other similar indices. We present a comprehensive empirical comparison between the χ-index and other bibliometric indices, focusing on a comparison with the h-index, by analysing two datasets—a large set of Google Scholar profiles and a small set of Nobel prize winners. Our results show that, although the χ and h indices are strongly correlated, they do exhibit significant differences. In particular, we show that, for these data sets, there are a substantial number of profiles for which χ is significantly larger than h. Furthermore, restricting these profiles to the cases when ck > k or ck < k corresponds to, respectively, classifying researchers as either tending to influential, i.e. having many more than h citations, or tending to prolific, i.e. having many more than h publications. [ABSTRACT FROM AUTHOR]

The Zagreb indices have been introduced more than forty years ago by I. Gutman, and N. Trinajstić and are defined asandin which degree of a vertexudenoted bydu. In the present study, we compute these Zagreb topological indices for a type of Benzenoid Systems “jagged-rectangle”. [ABSTRACT FROM PUBLISHER]

Doyle (circa 1980) found a formula for the number of $$k \times n$$ Latin rectangles $$L_{k,n}$$ . This formula remained dormant until it was recently used for counting $$k \times n$$ Latin rectangles, where $$k \in \{4,5,6\}$$ . We give a formal proof of Doyle's formula for arbitrary k. We also improve a previous implementation of this formula, which we use to find $$L_{k,n}$$ when $$k=4$$ and $$n \le 150$$ , when $$k=5$$ and $$n \le 40$$ and when $$k=6$$ and $$n \le 15$$ . Motivated by computational data for $$3 \le k \le 6$$ , some research problems and conjectures about the divisors of $$L_{k,n}$$ are presented. [ABSTRACT FROM AUTHOR]

The article focuses on solution of several mathematical problems. Topics discussed include values of a triangle's coordinates estimated by the use Pythagorean theorem, determination of empty space in a rectangular box filled with candles by subtraction of total volume of candles from total volume of the box, estimation of area of various regions in a triangle and finding area of trapezoid.

Abstract: A Skolem sequence of order is a sequence of integers such that (1) for all there are exactly two terms , such that , and (2) if and , then . Two Skolem sequences , are disjoint if implies that , for all . For example, the two Skolem sequences of order four and are disjoint. A set of pairwise disjoint Skolem sequences forms a Skolem rectangle of strength . The above sequences then form a Skolem rectangle of strength two: . We introduce several new constructions for Skolem and Rosa rectangles then we apply them to generate simple cyclic triple systems and disjoint cyclic triple systems. For example, for certain constants , we obtain disjoint Skolem sequences of order . Finally, we obtain the analogous results for hooked Skolem and Rosa sequences. [Copyright &y& Elsevier]

The article discusses the developments in the field of mathematics. It examines the problem involving the widest shelf of rectangular cross-section that can be inserted through a rectangular opening. It presents the possible solutions for the problem, including the quartic solution, the circular solution, and the root tracing solution.

Copyright of Gazi University Journal of Gazi Educational Faculty (GUJGEF) is the property of Gazi University Journal of Gazi Educational Faculty (GUJGEF) and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In a recent work "Arc-presentation of links: Monotonic simplification", Dynnikov shows that each rectangular diagram of the unknot, composite link, or split link can be monotonically simplified into a trivial, composite, or split diagram, respectively. The following natural question arises: Is it always possible to simplify monotonically a rectangular diagram of a satellite knot or link into one where the satellite structure is seen? Here we give a negative answer to that question both for knot and link cases. An example of a torus embedding that cannot be obtained from ordinary "thin" torus by methods of paper [2] is also constructed. [ABSTRACT FROM AUTHOR]

This article introduces spotlight tiling, a type of covering which is similar to tiling. The distinguishing aspects of spotlight tiling are that the 'tiles' have elastic size, and that the order of placement is significant. Spotlight tilings are decompositions, or coverings, and can be considered dynamic as compared to typical static tiling methods. A thorough examination of spotlight tilings of rectangles is presented, including the distribution of such tilings according to size, and how the directions of the spotlights themselves are distributed. The spotlight tilings of several other regions are studied, and suggest that further analysis of spotlight tilings will continue to yield elegant results and enumerations. [ABSTRACT FROM AUTHOR]

In this paper, the normal modes of an elastic rectangular waveguide are analyzed. We retrace the key aspects of the almost 150-year history of this problem. Using the superposition method, we have obtained an analytical solution of the problem for four types of symmetry of the wave field. In addition, we have established important differences of the dispersion characteristics of normal modes in a rectangle from the Rayleigh–Lamb modes for an infinite plate and the Pochhammer–Chree modes for a cylinder. We give also an estimate of a series of approximate theories for a rectangular waveguide. [ABSTRACT FROM AUTHOR]

We introduce the notion of cone rectangular metric space and prove Banach contraction mapping principle in cone rectangular metric space setting. Our result extends recent known results. [ABSTRACT FROM AUTHOR]

The inverse conduction problem arises when experimental measurements are taken in the interior of a body, and it is desired to calculate temperature on the surface. We consider the problem of finding, from the final data u(x, y, T) = φ(x, y), the initial data u(x, y, 0) of the temperature function u(x, y, t), (x, y) ∈ U ≡ (0, π) x (0, π), t ∈ [0, T] satisfying the nonlinear system ut - Δu = f(x, y, t, u(x, y, t)), (x, y, t) ∈ U x (0, T), u(0, y, t) = u(π, y, t) = u(x, 0, t) = u(x, π, t) = 0, (x, y, t) ∈ U x (0, T). This problem is known to be ill-posed, as the solution exhibits unstable dependence on the given data functions. Using the Fourier series method, we regularize the problem and to get some new error estimates. A numerical experiment is given. [ABSTRACT FROM AUTHOR]

The authors study a diffusive prey-predator model subject to the homogeneous Neumann boundary condition and give some qualitative descriptions of solutions to this reaction-diffusion system and its corresponding steady-state problem. The local and global stability of the positive constant steady-state are discussed, and then some results for non-existence of positive non-constant steady-states are derived. [ABSTRACT FROM AUTHOR]

Let v 1,..., v n be unit vectors in ℝ n such that v i ⋅ v j =− w for i≠ j, where $-1

The article discusses the symmetry types of rectangle and frieze patterns. It provides information on how many different symmetries does a rectangle have and what happens when it is combined with two of those symmetries. It highlights how can symmetry be used to differentiate designs. It also explores the property of isometries. Frieze patterns are designs contained between two parallel lines that extend infinitely in both directions, like an infinitely long flowered ribbon. An analysis of frieze patterns is also presented.

Copyright of RAIRO -- Operations Research is the property of EDP Sciences and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In [9], we proved numerically that spaces generated by linear combinations of some two-dimensional Haar functions exhibit unexpectedly nice orders of approximation for solutions of the single-layer potential equation in a rectangle. This phenomenon is closely related, on the one hand, to the properties of the approximation method of hyperbolic crosses and on the other to the existence of a strong singularity for solutions of such boundary integral equations. In the present paper, we establish several results on the approximation for the hyperbolic crosses and on the best N-term approximations by linear combinations of Haar functions in the H s -norms, −1 < s < 1/2; this provides a theoretical base for our numerical research. To the author's best knowledge, the negative smoothness case s < 0 was not studied earlier. [ABSTRACT FROM AUTHOR]

The paper deals with m by n rectangular arrays whose mn cells are filled with symbols. A section of the array consists of m cells, one from each row and no two from the same column. The paper focuses on the existence of sections that do contain symbols with high multiplicity. [ABSTRACT FROM AUTHOR]

The article presents several mathematical problems and their solutions proposed by various readers in New York. One of the problems is about finding the area of three points in a rectangle. Another problem asks for the expected number of rounds that the shootout in a National Hockey League (NHL) game will last if the probability of a shooter scoring a goal in a given round is 1/3.

It is shown that for any n disjoint axis-aligned fat rectangles in three-space there is a binary space partition (BSP) of O(n log8 n) size and O(log5 n) height and it can be constructed in O(n polylog n) time. This improves earlier bounds of Agarwal et al. [SIAM J. Comput., 29 (2000), pp. 1422-1448]. On the other hand, for every n ∊ N, there are n disjoint axis-aligned fat rectangles in R³ such that their smallest axis-aligned BSP has Ω(n log n) size. [ABSTRACT FROM AUTHOR]

Asaithambi, Zuhe, and Moore (Computing 28, 225–237, 1982) presented an algorithm to find good upper and lower bounds on the range of values of a function of several variables on an n- dimensional rectangle. Unfortunately, the algorithm presented there contains some errors. In this paper, we point out these errors, show how they may be corrected, and suggest improvements of the algorithm. [ABSTRACT FROM AUTHOR]

The article offers information on golden ratio, golden spiral and golden rectangle. It also presents several photographs where the exercises and examples related to golden ratio and golden rectangle were based. The golden ratio is also called golden section, golden mean, golden proportion, the extreme and main ratio as well as the divine proportion. A golden rectangle is a rectangle whose ratio of the lengths of sides a and b is equal to the golden ratio. Meanwhile, a golden spiral is a logarithmic curve which can be approximated by a Fibonacci spiral.

Abstract: We determine all simple perfect dissections of : rectangles into 13 : rectangular elements. A computer search shows there are 26 such dissections. Previous work yielded only eight such dissections into at most twelve rectangular elements. [Copyright &y& Elsevier]

We consider a problem to pack rectangles into several semi-infinite strips of certain widths. We suggest two simply realised online algorithms, that is, algorithms which pack rectangles just at the moments of their arrivals. It is shown that the accuracy of the former algorithm cannot be approximated by any absolute constant. The latter algorithm guarantees a constant multiplicative accuracy, and the obtained estimate of the multiplicative accuracy is unimprovable. The research was supported by the Russian Foundation for Basic Research, grant 05–01–00798. [ABSTRACT FROM AUTHOR]

In this paper we propose and justify at the differential level an iteration method for solving the Stokes problem in a rectangular domain with the rate of convergence independent of the ratio of the sides. The numerical implementation of the algorithm is constructed for the cavity test problem and computational results are given. [ABSTRACT FROM AUTHOR]

The article discusses the process of tiling deficient rectangles through the utilization of L-shaped tetrominoes. It states that a tetromino is a kind of polyomino comprised of plane squares. Furthermore, L-shaped tetromino is composed of four 1 x 1 squares where the removal of one 1 x 1 square forms the deficient rectangle. It was found that deficient triangles having an area divisible by eight are capable of being tiled. Also, a discussion on tiling a deficient board was given.

Examines the mathematical method used by a farmer in building an animal cage with a volume of up to 50 cubic feet. Use of the basic calculus optimization problem of finding the minimum perimeter of a rectangle given a fixed area; Discovery of the most efficient way of building an animal cage; Consideration of the volume of the surface area.

Presents several mathematical problems for middle school students. Rectangle with unequal sides; Value of items spent based on a change received from the transaction; Division of cartons.

We establish necessary and sufficient conditions on the five positive real numbers a, b, c, u, v for a rectangle with sides u, v to fit in a triangle with sides a, b, c, and we note a few curious consequences. [ABSTRACT FROM AUTHOR]

We investigate the problem of permuting a sparse rectangular matrix into block-diagonal form. Block-diagonal form of a matrix grants an inherent parallelism for solving the deriving problem, as recently investigated in the context of mathematical programming, LU factorization, and QR factorization. To represent the nonzero structure of a matrix, we propose bipartite graph and hypergraph models that reduce the permutation problem to those of graph partitioning by vertex separator and hypergraph partitioning, respectively. Our experiments on a wide range of matrices, using the state-of-the-art graph and hypergraph partitioning tools MeTiS and PaToR, revealed that the proposed methods yield very effective solutions both in terms of solution quality and runtime. [ABSTRACT FROM AUTHOR]

We study how many values of an unknown integer-valued function f one needs to know in order to find a local maximum of f. We consider functions defined on finite subsets of discrete plane. We prove upper bounds for functions defined on rectangles and present lower bounds for functions defined on arbitrary domains in terms of the size of the domain and the size of its border. [Copyright &y& Elsevier]

Presents problems and solutions concerning mathematics. Centroid-circumcenter distance; Maximum area possible for a rectangle; Functionally related convergents; Triangle inequalities; Hypergeometric representations.

Analyzes mathematician Prince Rupert's rectangles. Euclidean space; Central symmetry; Aspect ratio; Centered maximal rectangles; Related lemmas and corollaries.

In this paper, we show that every sequence of rectangles whose side lengths are not greater than a and whose total area is not greater than ab/2 can be packed into the rectangle of a x b, where a ≥ b. [ABSTRACT FROM AUTHOR]