Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

Transversal of disjoint convex polygons

Given a set S of n disjoint convex polygons {P_i∣1?i?n} in a plane, each with k_i vertices, the transversal problem is to find, if there exists one, a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑_i=1ⁿk_i is the total number of vertices of the polygons.     

Efficient algorithm for transversal of disjoint convex polygons

Given a set S of n disjoint convex polygons {P_i∣1?i?n} in a plane, each with k_i vertices, the transversal problem is to determine whether there exists a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N+nlogn) time, where N=∑_i=1ⁿk_i is the total number of vertices of the polygons.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

Kernel bounds for disjoint cycles and disjoint paths

In this paper, we show that the problems Disjoint Cycles and Disjoint Paths do not have polynomial kernels, unless NP⊆coNP/poly. Thus, these problems do not allow polynomial time preprocessing that results in instances whose size is bounded by a polynomial in the parameter at hand. We build upon recent results by Bodlaender et al. [6] and Fortnow and Santhanam [20], that show that NP-complete problems that are ‘or-compositional’ do not have polynomial kernels, unless NP⊆coNP/poly. To this machinery, we add a notion of transformation, and obtain that Disjoint Cycles, and Disjoint Paths do not have polynomial kernels, unless NP⊆coNP/poly. For the proof, we introduce a problem on strings, called Disjoint Factors, and first show that this problem has no polynomial kernel unless NP⊆coNP/poly. We also show that the related Disjoint Cycles Packing problem has a kernel of size O(klogk).     

On partitioning rectilinear polygons into star-shaped polygons

We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.     

On partitioning rectilinear polygons into star-shaped polygons

We present an algorithm for finding optimum partitions of simple monotone rectilinear polygons into star-shaped polygons. The algorithm may introduce Steiner points and its time complexity isO(n), wheren is the number of vertices in the polygon. We then use this algorithm to obtain anO(n logn) approximation algorithm for partitioning simple rectilinear polygons into star-shaped polygons with the size of the partition being at most six times the optimum.     

Fourier polygons

Polygons are everywhere, but one place the author didn't expect to see polygons is in the Fourier transform, but he found them there as well. The Fourier transform is an indispensable tool in signal processing. In computer graphics, it helps us understand and cure problems as diverse as jaggies on the edge of polygons, blocky looking textures, and animated objects that appear to jump erratically as they move across the screen. His friend and colleague Alvy Ray Smith recently wrote a memo that demonstrated a surprising interpretation of the Fourier transform. He showed how in some circumstances the Fourier transform looks like nothing more than operations on regular polygons. The article is about that fascinating insight. He starts off with by using complex numbers to do geometry and then moves on to the Fourier series, building up to a discussion of the new interpretation     

Note on covering monotone orthogonal polygons with star-shaped polygons

In 1986, Keil provided an O(n²) time algorithm for the problem of covering monotone orthogonal polygons with the minimum number of r-star-shaped orthogonal polygons. This was later improved to O(n) time and space by Gewali et al. in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63]. In this paper we simplify the latter algorithm—we show that with a little modification, the first step Sweep1 of the discussed algorithm—which computes the top ceilings of horizontal grid segments—can be omitted.In addition, for the minimum orthogonal guard problem in the considered class of polygons, our approach provides a linear time algorithm which uses O(k) additional space, where k is the size of the optimal solution—the algorithm in [L. Gewali, M. Keil, S.C. Ntafos, On covering orthogonal polygons with star-shaped polygons, Information Sciences 65 (1992) 45-63] uses both O(n) time and O(n) additional space.     

Reductions between disjoint NP-Pairs

Disjoint NP-pairs are pairs (A, B) of nonempty, disjoint sets in NP. We prove that all of the following assertions are equivalent: There is a many-one complete disjoint NP-pair; there is a strongly many-one complete disjoint NP-pair; there is a Turing complete disjoint NP-pair such that all reductions are smart reductions; there is a complete disjoint NP-pair for one-to-one, invertible reductions; the class of all disjoint NP-pairs is uniformly enumerable. Let A, B, C, and D be nonempty sets belonging to NP. A smart reduction between the disjoint NP-pairs (A, B) and (C, D) is a Turing reduction with the additional property that if the input belongs to A B, then all queries belong to C D. We prove under the reasonable assumption that UP ∩ co-UP has a P-bi-immune set that there exist disjoint NP-pairs (A, B) and (C, D) such that (A, B) is truth-table reducible to (C, D), but there is no smart reduction between them. This paper contains several additional separations of reductions between disjoint NP-pairs. We exhibit an oracle relative to which DistNP has a truth-table-complete disjoint NP-pair, but has no many-one-complete disjoint NP-pair.     

Instant Visibility

We present an online occlusion culling system which computes visibility in parallel to the rendering pipeline. We show how to use point visibility algorithms to quickly calculate a tight potentially visible set (PVS) which is valid for several frames, by shrinking the occluders used in visibility calculations by an adequate amount. These visibility calculations can be performed on a visibility server, possibly a distinct computer communicating with the display host over a local network. The resulting system essentially combines the advantages of online visibility processing and region-based visibility calculations, allowing asynchronous processing of visibility and display operations. We analyze two different types of hardware-based point visibility algorithms and address the problem of bounded calculation time which is the basis for true real-time behavior. Our results show reliable, sustained 60 Hz performance in a walkthrough with an urban environment of nearly 2 million polygons, and a terrain flyover.     

Least-squares fitting of polygons

Fitting a polygon to a set of given points in the plane is a problem which may arise in certain engineering, computer graphics or scientific applications. This paper presents an algorithm which computes a continuous function closely approximating various polygons, for which the sum of the squares of the distance to the given set of points is minimized.     

Context-Sensitive Visibility

An improvement to the so-called visual verification approach is presented. Visual verification is a method for checking the correctness of the behaviour of a reactive or concurrent system. It shares a great deal of common ground with ordinary formal state space verification, but is more user-friendly. This is because the user does not need to specify in detail the properties that the system must satisfy to be correct. Instead, the user only lists the atomic actions that are relevant for the property. Computer tools are used to obtain a graphical representation which is a summary of all possible alternative behaviours of the system, and the user then analyses the result. The improvement presented in this article allows the user to pick a region of the graphical representation and investigate it in more detail, without being overwhelmed by the details outside the region. The improvement is illustrated by analysing the livelocks in a model of the alternating bit protocol.     

Scale preserving smoothing of polygons

A smoother version of a polygon ? is defined as a polygon which approximates ? according to a given criterion and which simultaneously has no more edges than ? itself. In this paper, a scale preserving smoothing algorithm is presented. The input to the algorithm is a polygon ? and the output is its smoothed version ?. ?, which contains all the scale information that ? contains, is called the linear minimum perimeter polygon (LMPP) of ? within a tolerance of. Using the quantity the degree of with ? approximates ? can be controlled. From the LMPP a representation for a polygon approximating ? can be procured, which is invariant to scale and translation changes. Examples of smoothing maps and characters have been presented.     

Competitive exploration of rectilinear polygons

Exploring a polygon with robots when the robots do not have knowledge of the surroundings can be viewed as an online problem. Typical for online problems is that decisions must be made based on past events without complete information about the future. In our case the robots do not have complete information about the environment. Competitive analysis can be used to measure the performance of methods solving online problems. The competitive ratio of such a method is the ratio between the method's performance and the performance of the best method having full knowledge of the future. We prove constant competitive strategies and lower bounds for exploring a simple rectilinear polygon in the _L1$L_1$ metric.     

On triangulation axes of polygons

We propose the triangulation axis as an alternative skeletal structure for a simple polygon P. This axis is a straight-line tree that can be interpreted as an anisotropic medial axis of P, where inscribed disks are line segments or triangles. The underlying triangulation that specifies the anisotropy can be varied, to adapt the axis so as to reflect predominant geometrical and topological features of P. Triangulation axes typically have much fewer edges and branchings than the Euclidean medial axis or the straight skeleton of P. Still, they retain important properties, as for example the reconstructability of P   from its skeleton. Triangulation axes can be computed from their defining triangulations in O(n)$O(n)$ time. We investigate the effect of using several optimal triangulations for P  . In particular, careful edge flipping in the constrained Delaunay triangulation leads, in O(nlog?n)$O(n\log ?n)$ overall time, to an axis competitive to ‘high quality axes’ requiring Θ(n³)$\Theta (n^3)$ time for optimization via dynamic programming.     

Efficient triangulation of simple polygons

This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a newadaptive algorithm for triangulating a simplen-sided polygon. The algorithm runs in timeO(n(1+t _o)) witht ₀<n. The quantityt ₀ measures theshape-complexity of thetriangulation delivered by the algorithm. More preciselyt ₀ is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of theinput polygon. Although the worst-case complexity of the algorithm isO(n ²), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where thecomputational complexity is a function of theoutput complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.     

节点约束型链路分离算法

针对节点约束型链路分离问题中的两条链路需经过各自必经点集的特点,提出一种以遗传算法和迪杰斯特拉算法为基础的节点约束型链路分离算法。通过改进的遗传算法得到较优的必经点序列,利用带有禁忌搜索的迪杰斯特拉最短距离算法求必经点对之间的无环最短路径,采用禁忌边的方式保证路径间重边最少。得到起点到终点之间的两条受必经点约束的路径,路径内无环路、路径间重边最少。大量模拟仿真实验结果表明了该算法的有效性和可行性。     

On constructing disjoint linear codes

To produce a highly nonlinear resilient function, the disjoint linear codes were originally proposed by Johansson and Pasalic in IEEE Trans. Inform. Theory, 2003, 49(2): 494–501. In this paper, an effective method for finding a set of such disjoint linear codes is presented. When n ⩾ 2k, we can find a set of [n,k]disjoint linear codes with cardinality 2^n-k +⌊(n-k)/k⌊; When n < 2k, no set of disjoint linear codes exists with cardinality at least 2. We also describe a result on constructing a set of [n, k] disjoint linear codes with minimum distance at least some fixed positive integer.     

Rectilinearity measurements for polygons

The paper introduces a shape measure intended to describe the extent to which a closed polygon is rectilinear. Other than somewhat obvious measures of rectilinearity (e.g., the sum of the differences of each corner's angle from multiples of 90/spl deg/), there has been little work in deriving a measure that is straightforward to compute, is invariant under scale, rotation, and translation, and corresponds with the intuitive notion of rectilinear shapes. There are applications in a number of different areas of computer vision and photogrammetry. Rectilinear structures often correspond to human-made objects and are therefore justified as attentional cues for further processing. For instance, in aerial image processing and reconstruction, where building footprints are often rectilinear on the local ground plane, building structures, once recognized as rectilinear, can be matched to corresponding shapes in other views for stereo reconstruction. Perceptual grouping algorithms may seek to complete shapes based on the assumption that the object in question is rectilinear. Using the proposed measure, such systems can verity this assumption.