Generating and counting valid patterns in routes between two points

Given two points on a plane, any rectilinear route between them can be specified by directions and lengths of constituent line segments. A word (pattern) over the alphabetN, E, S, andW is defined to represent a sequence of directions. The length of each line segment is ignored. In this paper we characterize and count all valid words, that is, those words representing non-selfcrossing routes.Notation V _n The set of all valid words of lengthn. - P ⁿ The set of all words of lengthn.     

Some geometric applications of Dilworth’s theorem

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are collinear. We settle an old question of Avital, Hanani, Erdős, Kupitz, and Perles by showing that every geometric graph withn vertices andm>k ⁴ n edges containsk+1 pairwise disjoint edges. We also prove that, given a set of pointsV and a set of axis-parallel rectangles in the plane, then either there arek+1 rectangles such that no point ofV belongs to more than one of them, or we can find an at most 2·10⁵ k ⁸ element subset ofV meeting all rectangles. This improves a result of Ding, Seymour, and Winkler. Both proofs are based on Dilworth’s theorem on partially ordered sets. The research by János Pach was supported by Hungarian National Foundation for Scientific Research Grant OTKA-4269 and NSF Grant CCR-91-22103.     

Pointed binary encompassing trees: Simple and optimal

For n disjoint line segments in the plane we construct in optimal O(nlogn) time and linear space an encompassing tree of maximum degree three such that at every vertex v all edges of the tree that are incident to v lie in a halfplane bounded by the line through the input segment which v is an endpoint of. In particular, this tree is pointed since every vertex has an incident angle greater than π. Such a pointed binary tree can be augmented to a minimum pseudo-triangulation. It follows that every set of disjoint line segments in the plane has a constrained minimum pseudo-triangulation whose maximum vertex degree is bounded by a constant.     

Every Set of Disjoint Line Segments Admits a Binary Tree

Given a set of n disjoint line segments in the plane, we show that it is always possible to form a tree with the endpoints of the segments such that each line segment is an edge of the tree, the tree has no crossing edges, and the maximum vertex degree of the tree is 3. Furthermore, there exist configurations of line segments where any such tree requires degree 3. We provide an O(nlog n) time algorithm for constructing such a tree, and show that this is optimal. Received September 14, 1999, and in revised form January 17, 2001. Online publication August 29, 2001.     

Polyhedral line transversals in space

Algorithms are developed for determining if a set of polyhedral objects inR ³ can be intersected by a common transversal (stabbing) line. It can be determined inO(n logn) time if a set ofn line segments in space has a line transversal, and such a transversal can be found in the same time bound. For a set of polyhedra with a total ofn vertices, we give anO(n ⁴ logn) algorithm for determining the existence of, and computing, a line transversal. Helly-type theorems for lines and segments are also given. In particular, it is shown that if every six of a set of lines in space are intersected by a common transversal, then the entire set has a common transversal.     

ON STABLE LINE SEGMENTS IN ALL TRIANGULATIONS OF A PLANAR POINT SET

Abstract. Let S be a set of finite plauar points. A llne segment L(p, q) with p, q E Sis called a stable line segment of S, if there is no Line segment with two endpoints in S intersecting L(p, q). In this paper, some geometric properties of the set of all stable line segments     

Efficiently updating constrained Delaunay triangulations

TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629.     

AnO(n logn) algorithm for the voronoi diagram of a set of simple curve segments

LetX be a given set ofn circular and straight line segments in the plane where two segments may interest only at their endpoints. We introduce a new technique that computes the Voronoi diagram ofX inO(n logn) time. This result improves on several previous algorithms for special cases of the problem. The new algorithm is relatively simple, an important factor for the numerous practical applications of the Voronoi diagram.This work was supported by NSF Grants No. DCR-84-01898 and No. DCR-84-01633.     

Dynamic Point Location in General Subdivisions

The dynamic planar point location problem is the task of maintaining a dynamic set S of n nonintersecting (except possibly at endpoints) line segments in the plane under the following operations:

• Locate (: point): Report the segment immediately above , i.e., the first segment intersected by an upward vertical ray starting at ;

• Insert (: segment): Add segment to the collection of segments;

• Delete (: segment): Remove segment from the collection of segments.

We present a solution which requires space O(n) and has query and insertion time O(log n log log n) and deletion time O(log²n). The bounds for insertions and deletions are amortized. A query time below O(log²n) was previously only known for monotone subdivisions and subdivisions consisting of horizontal segments and required nonlinear space.     

A Note on Binary Plane Partitions

Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

On the classification of linear spaces of order 11

A linear space of order n is a pair (V,B), where V is a finite set of n elements and B is a set of subsets of V such that each 2-subset of V is contained in exactly one element of B. The exact number of nonisomorphic linear spaces was known up to order 10. Betten and Braun [1] found that there exist at least 232,923 nonisomorphic linear spaces of order 11. We used a generalization of Ivanov's algorithm for the enumeration of block designs in order to construct all 232,929 linear spaces of order 11. The method used will be described and some data concerning line types, line lengths, and orders of automorphism groups is listed. © 1995 John Wiley & Sons, Inc.     

Bimodules associated to vertex operator algebras

Let V be a vertex operator algebra and m, n ≥ 0. We construct an A _n (V)-A _m (V)-bimodule A _n,m (V) which determines the action of V from the level m subspace to level n subspace of an admissible V-module. We show how to use A _n,m (V) to construct naturally admissible V-modules from A _m (V)-modules. We also determine the structure of A _n,m (V) when V is rational. Chongying Dong was supported by NSF grants, China NSF grant 10328102 and a Faculty research grant from the University of California at Santa Cruz. Cuipo Jiang was supported in part by China NSF grant 10571119.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

Projective normality of G.I.T. quotient varieties modulo finite groups

We prove that for any finite dimensional representation V of a finite group G of order n the quotient variety G??(V) is projectively normal with respect to descent of 𝒪(1)^?l where l = lcm{1,2,3,4,…,n}. We also prove that for the tautological representation V of the alternating group A_n the projective variety A_n??(V) is projectively normal with respect to the descent of the above line bundle.     

Bruhat Order for Two Flags and a Line

The classical Ehresmann-Bruhat order describes the possible degenerations of a pair of flags in a linear space V under linear transformations of V; or equivalently, it describes the closure of an orbit of GL(V acting diagonally on the product of two flag varieties.We consider the degenerations of a triple consisting of two flags and a line, or equivalently the closure of an orbit of GL(V) acting diagonally on the product of two flag varieties and a projective space. We give a simple rank criterion to decide whether one triple can degenerate to another. We also classify the minimal degenerations, which involve not only reflections (i.e., transpositions) in the Weyl group S_VSn = dim(V, but also cycles of arbitrary length. Our proofs use only elementary linear algebra and combinatorics.     

A Note on Binary Plane Partitions

   Abstract. This paper considers binary space partition s (BSP for short) for disjoint line segments in the plane. The BSP for a disjoint set of objects is a scheme dividing the space recursively by hyperplanes until the resulting fragments of objects are separated. The size of a BSP is the number of resulting fragments of the objects. We show that the minimal size of a BSP for n disjoint line segments in the plane is Ω (n log n /log log n) in the worst case.     

Alternating Paths along Axis-Parallel Segments

It is shown that for a set S of n pairwise disjoint axis-parallel line segments in the plane there is a simple alternating path of length . This bound is best possible in the worst case. In the special case that the n pairwise disjoint axis-parallel line segments are protruded (that is, if the intersection point of the lines through every two nonparallel segments is not visible from both segments), there is a simple alternating path of length n. Work on this paper was partially supported by National Science Foundation grants CCR-0049093 and IIS-0121562. A preliminary version of this paper has appeared in the Proceedings of the 8th International Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of Lecture Notes on Computer Science, Springer, Berlin, 2003, pp. 389–400.     

Computing simple circuits from a set of line segments

We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.     

Union curvature of a vector field in a subspace

The differential equations of union curves on a hypersurfaceV _n immersed in a RiemannianV _n+1 have been obtained by Springer [1]. These results were generalized later for a subspace in a Riemannian space by Mishra [2]. The author [3] has defined the union curvature of a vector field with respect to a curve on a hypersurfaceV _n of a RiemannianV _n+1. The purpose of this paper is to consider union curvature of a vector field with respect to a curve in a subspaceV _n of a RiemannianV _m. The author is indebted to the referee for helpful suggestions.     

Almost Injective Transformations of an Infinite Set

Let V be an infinite-dimensional vector space, let n be a cardinal such that ?₀ ≤ n ≤ dim V, and let AM(V, n) denote the semigroup consisting of all linear transformations of V whose nullity is less than n. In recent work, Mendes-Gonçalves and Sullivan studied the ideal structure of AM(V, n). Here, we do the same for a similarly-defined semigroup AM(X, q) of transformations defined on an infinite set X. Although our results are clearly comparable with those already obtained for AM(V, n), we show that the two semigroups are never isomorphic.