Simply connected orthogonal polygons as unions of two orthogonally starshaped sets

Let S be a simply connected orthogonal polygon in the plane. The set S is a union of two sets which are starshaped via staircase paths (i.e., orthogonally starshaped) if and only if for every three points of S, at least two of these points see (via staircase paths) a common point of S. Moreover, the simple connectedness condition cannot be deleted.     

Intersections and Unions of Orthogonal Polygons Starshaped Via Staircase n-Paths

For n ≥ 1, define p (n) to be the smallest natural number r for which the following is true: For any finite family of simply connected orthogonal polygons in the plane and points x and y in , if every r (not necessarily distinct) members of contain a common staircase n-path from x to y, then contains such a path. We show that p(1) = 1 and p(n) = 2 (n − 1) for n ≥ 2. The numbers p(n) yield an improved Helly theorem for intersections of sets starshaped via staircase n-paths. Moreover, we establish the following dual result for unions of these sets: Let be any finite family of orthogonal polygons in the plane, with simply connected. If every three (not necessarily distinct) members of have a union which is starshaped via staircase n-paths, then T is starshaped via staircase (n + 1)-paths. The number n + 1 in the theorem is best for every n ≥ 2.     

The dimension of the kernel in an intersection of starshaped sets

We establish the following Helly-type theorem: Let ${\cal K}$ be a family of compact sets in $\mathbb{R}^d$. If every d + 1 (not necessarily distinct) members of ${\cal K}$ intersect in a starshaped set whose kernel contains a translate of set A, then $\cap \{ K : K\; \hbox{in}\; {\cal K} \}$ also is a starshaped set whose kernel contains a translate of A. An analogous result holds when ${\cal K}$ is a finite family of closed sets in $\mathbb{R}^d$. Moreover, we have the following planar result: Define function f on $\{0, 1, 2\}$ by f(0) = f(2) = 3, f(1) = 4. Let ${\cal K}$ be a finite family of closed sets in the plane. For k = 0, 1, 2, if every f(k) (not necessarily distinct) members of ${\cal K}$ intersect in a starshaped set whose kernel has dimension at least k, then $\cap \{K : K\; \hbox{in}\; {\cal K}\}$ also is a starshaped set whose kernel has dimension at least k. The number f(k) is best in each case.Received: 4 June 2002     

Intersection of maximal orthogonally starshaped polygons

Let S be a simply connected orthogonal polygon in and let P(S) denote the intersection of all maximal starshaped via staircase paths orthogonal subpolygons in S. Our result: if , then there exists a maximal starshaped via staircase paths orthogonal polygon , such that . As a corollary, P(S) is a starshaped (via staircase paths) orthogonal polygon or empty. The results fail without the requirement that the set S is simply connected. Received 1 March 1999.     

Families of planar sets having starlike union

Let be a finite family of compact sets in the plane, and letk be a fixed natural number. If every three (not necessarily distinct) members of have a union which is simply connected and starshaped viak-paths, then and is starshaped viak-paths. Analogous results hold for paths of length at most , > 0, and for staircase paths, although not for staircasek-paths.Supported in part by NSF grant DMS-9504249     

A Helly-type theorem for countable intersections of starshaped sets

Let k and d be fixed integers, 0kd, and let be a collection of sets in If every countable subfamily of has a starshaped intersection, then is (nonempty and) starshaped as well. Moreover, if every countable subfamily of has as its intersection a starshaped set whose kernel is at least k-dimensional, then the kernel of is at least k-dimensional, too. Finally, dual statements hold for unions of sets.Received: 3 April 2004     

A Krasnosel’skii-type theorem for paths of bounded length

Let S be a nonempty closed, simply connected set in the plane, and let α τ; 0. If every three points of 5 see a common point of S via paths of length at most α, then for some point s0 of S, s0 sees each point of S via such a path. That is, S is starshaped via paths of length at most α. Supported in part by NSF grant DMS-9207019     

Helly-type theorems for intersections of sets starshaped via orthogonally convex paths

Let ${\mathcal{K}}$ be a family of simply connected sets in the plane. If every countable subfamily of ${\mathcal{K}}$ has an intersection that is starshaped via orthogonally convex paths, then ${\mathcal{K}}$ itself has such an intersection. For the d-dimensional case, let ${\mathcal{K}}$ be a family of compact sets in ${\mathbb{R}^d}$ . If every finite subfamily of ${\mathcal{K}}$ has an intersection that is starshaped via orthogonally convex paths, again ${\mathcal{K}}$ itself has such an intersection.     

Intersections of Sets Starshaped Via Paths of Bounded Length

 Let S be a nonempty closed, simply connected set in the plane. For α > 0, let ℳ denote the family of all maximal subsets of S which are starshaped via paths of length at most α. Then ⋂{M : M in ℳ} is either starshaped via α-paths or empty. The result fails without the simple connectedness condition. However, even with a simple connectedness requirement, there is no Helly theorem for intersections of sets which are starshaped via α-paths. Received November 19, 2001; in revised form April 25, 2002 Published online November 18, 2002     

Unions of orthogonally convex or orthogonally starshaped polygons

LetT be a simply connected orthogonal polygon having the property that for every three points ofT, at least two of these points see each other via staircases inT. ThenT is a union of three orthogonally convex polygons. The number three is best possible.ForT a simply connected orthogonal polygon,T is a union of two orthogonally convex polygons if and only if for every sequencev ₁,...,v _n,v _n+1 =v ₁ inT, n odd, at least one consecutive pairv _i ,v _i+1 sees each other via staircase paths inT, 1 i n. An analogous result says thatT is a union of two orthogonal polygons which are starshaped via staircase paths if and only if for every odd sequence inT, at least one consecutive pair sees a common point via staircases inT.Supported in part by NSF grants DMS-8908717 and DMS-9207019.     

A visible shoreline theorem for staircase paths

Let C be an orthogonal polygon in the plane, bounded by a simple closed curve, and assume that C is starshaped via staircase paths. Let P í \mathbbR²\(int C)P \subseteq {\mathbb{R}}^2\backslash({\rm int} C). If every four points of P see a common boundary point of C via staircase paths in \mathbbR²\(int C){\mathbb{R}}^2\backslash({\rm int} C), then there is a boundary point b of C such that every point of P sees b (via staircase paths in \mathbbR²\(int C){\mathbb{R}}^2\backslash({\rm int} C)). The number four is best possible, even if C is orthogonally convex.     

A Helly-type theorem for intersections of orthogonally starshaped sets in \mathbb R^d

Let $\mathcal K$ be a finite family of orthogonal polytopes in $\mathbb R^d$ such that, for every nonempty subfamily $\mathcal K^\prime $ of $\mathcal K, \cap \{K : K$ in $\mathcal K^\prime \}$ , if nonempty, is a finite union of boxes whose intersection graph is a tree. Assume that every $d + 1$ (not necessarily distinct) members of $\mathcal K$ meet in a (nonempty) staircase starshaped set. Then $S \equiv \cap \{ K : K$ in $\mathcal K\}$ is nonempty and staircase starshaped.     

阶极小渐近基

Let N denote the set of all nonnegative integers and A be a subset of N.Let W be a nonempty subset of N.Denote by F~*(W) the set of all finite,nonempty subsets of W.Fix integer g≥2,let A_g(W) be the set of all numbers of the form sum f∈Fa_fg~f where F∈F~*(W)and 1≤a_f≤g-1.For i=0,1,2,3,let W_i = {n∈N|n≡ i(mod 4)}.In this paper,we show that the set A = U_i~3=0 A_g(W_i) is a minimal asymptotic basis of order four.     

Intersections of maximal staircase sets

A compact set is staircase connected if every two points a, b ∈ S can be connected by an x-monotone and y-monotone polygonal path with sides parallel to the coordinate axes. In [5] we have introduced the concepts of staircase k-stars and kernels. In this paper we prove that if the staircase k-kernel is not empty, then it can be expressed as the intersection of a covering family of maximal subsets of staircase diameter k of S.      

ERGODIC THEOREMS FOR NON-LIPSCHITZIAN SEMIGROUPS WITHOUT CONVEXITY

§１．ＩｎｔｒｏｄｕｃｔｉｏｎＬｅｔＨｂｅａＨｉｌｂｅｒｔｓｐａｃｅｗｉｔｈｎｏｒｍ‖·‖ａｎｄｉｎｎｅｒｐｒｏｄｕｃｔ（·，·）ａｎｄｌｅｔＣｂｅａｎｏｎｅｍｐｔｙｓｕｂｓｅｔｏｆＨ．ＡｍａｐｐｉｎｇＴ：Ｃ｜→ＣｉｓｓａｉｄｔｏｂｅＬｉｐｓｃｈｉｔ...     

A Helly-type theorem for simple polygons

Let be a family of simple polygons in the plane. If every three (not necessarily distinct) members of have a simply connected union and every two members of have a nonempty intersection, then {P:P in } . Applying the result to a finite family of orthogonally convex polygons, the set {C:C in } will be another orthogonally convex polygon, and, in certain circumstances, the dimension of this intersection can be determined.Supported in part by NSF grant DMS-9207019.     

The dimension of the kernel in finite and infinite intersections of starshaped sets

Summary. We establish the following Helly-type result for infinite families of starshaped sets in Define the function f on {1, 2} by f(1) = 4, f(2) = 3. Let be a fixed positive number, and let be a uniformly bounded family of compact sets in the plane. For k = 1, 2, if every f(k) (not necessarily distinct) members of intersect in a starshaped set whose kernel contains a k-dimensional neighborhood of radius , then is a starshaped set whose kernel is at least k-dimensional. The number f(k) is best in each case. In addition, we present a few results concerning the dimension of the kernel in an intersection of starshaped sets in Some of these involve finite families of sets, while others involve infinite families and make use of the Hausdorff metric.     

A Krasnosel’skii-type result for planar sets starshaped via orthogonally convex paths

A Krasnosel’skii-type theorem for compact sets that are starshaped via staircase paths may be extended to compact sets that are starshaped via orthogonally convex paths: Let S be a nonempty compact planar set having connected complement. If every two points of S are visible via orthogonally convex paths from a common point of S, then S is starshaped via orthogonally convex paths. Moreover, the associated kernel Ker S has the expected property that every two of its points are joined in Ker S by an orthogonally convex path. If S is an arbitrary nonempty planar set that is starshaped via orthogonally convex paths, then for each component C of Ker S, every two of points of C are joined in C by an orthogonally convex path. Communicated by Imre Bárány     

High-Dimensional Shape Fitting in Linear Time

Let $P$ be a set of $n$ points in $\Re^d$. The {\em radius} of a $k$-dimensional flat ${\cal F}$ with respect to $P$, which we denote by ${\cal RD}({\cal F},P)$, is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where $\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between $p$ and its projection onto ${\cal F}$. The $k$-flat radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the minimum, over all $k$-dimensional flats ${\cal F}$, of ${\cal RD}({\cal F},P)$. We consider the problem of computing ${R^{\rm opt}_k}(P)$ for a given set of points $P$. We are interested in the high-dimensional case where $d$ is a part of the input and not a constant. This problem is NP-hard even for $k = 1$. We present an algorithm that, given $P$ and a parameter $0 < \eps \leq 1$, returns a $k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 + \eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that depends only on $\eps$ and $k$. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of $d n^{O(k/\eps^c)}$, where $c$ is an appropriate constant.     

Unions of Sets Starshaped via Staircase Paths or via Paths of Bounded Length

Let S be an orthogonal polygon in the plane, S simply connected, and let k=2,3. Set S is a union of k sets starshaped via staircase paths if and only if for every F finite, F bdry S, there is a set G bdry S arbitrarily close to F and points si,1 ik, (depending on G) such that each point of G is clearly visible from some si. An analogous result holds for a union of 2 sets starshaped via -paths when S is a closed simply connected set in the plane. Each result is best possible.