Nearest Neighbor Queries in Metric Spaces

Given a set S of n sites (points), and a distance measure d , the nearest neighbor searching problem is to build a data structure so that given a query point q , the site nearest to q can be found quickly. This paper gives data structures for this problem when the sites and queries are in a metric space. One data structure, D(S) , uses a divide-and-conquer recursion. The other data structure, M(S,Q) , is somewhat like a skiplist. Both are simple and implementable. The data structures are analyzed when the metric space obeys a certain sphere-packing bound, and when the sites and query points are random and have distributions with an exchangeability property. This property implies, for example, that query point q is a random element of . Under these conditions, the preprocessing and space bounds for the algorithms are close to linear in n . They depend also on the sphere-packing bound, and on the logarithm of the distance ratio of S , the ratio of the distance between the farthest pair of points in S to the distance between the closest pair. The data structure M(S,Q) requires as input data an additional set Q , taken to be representative of the query points. The resource bounds of M(S,Q) have a dependence on the distance ratio of S Q . While M(S,Q) can return wrong answers, its failure probability can be bounded, and is decreasing in a parameter K . Here K≤ |Q|/n is chosen when building M(S,Q) . The expected query time for M(S,Q) is O(Klog n)log , and the resource bounds increase linearly in K . The data structure D(S) has expected O( log n) ^O(1) query time, for fixed distance ratio. The preprocessing algorithm for M(S,Q) can be used to solve the all nearest neighbor problem for S in O(n(log n) ² (log ϒ(S)) ² ) expected time. Received September 17, 1996, and in revised form November 1, 1998.     

Complex hyperbolic hyperplane complements

We study spaces obtained from a complete finite volume complex hyperbolic n-manifold M by removing a compact totally geodesic complex (n − 1)-submanifold S. The main result is that the fundamental group of M\ S{M{\setminus} S} is relatively hyperbolic, relative to fundamental groups of the ends of M\ S{M{\setminus} S} , and M\ S{M{\setminus} S} admits a complete finite volume A-regular Riemannian metric of negative sectional curvature. It follows that for n > 1 the fundamental group of M\ S{M{\setminus} S} satisfies Mostow-type Rigidity, has solvable word and conjugacy problems, has finite asymptotic dimension and rapid decay property, satisfies Borel and Baum-Connes conjectures, is co-Hopf and residually hyperbolic, has no nontrivial subgroups with property (T), and has finite outer automorphism group. Furthermore, if M is compact, then the fundamental group of M\ S{M{\setminus} S} is biautomatic and satisfies Strong Tits Alternative.     

A Note on the characterization of Shannon-Wiener’s measure of information

Summary In [1] the author treated a characterization problem of the ShannonWiener measure of information for continuous probability distributions defined over an abstract measure space (R, S, m), wherem is a σ-finite measure over a σ-field S of subsets ofR, whose rangeM(S) is such thatM(S)=[0, ∞]. This condition on the range of the basic measure, however, can slightly be altered such thatM(S)=[0,1], and this modification is useful for characterization of the Kullback-Leibler mean information. In the present paper, it is shown that the characterization procedure of [1] can be applicable to continuous probability distributions defined on a finite measure space.     

Quasi-duality for the rings of generalized power series *

Let A, B be associative rings with identity, and (S, ≤) a strictly totally ordered commutative monoid which is also artinian. For any bimodule _AM_B , we construct a bimodule _A[[S]]M[S]_B[[S]] and prove that _AM_B defines a quasi-duality if and only if the bimodule _A[[S]]M[S]_B[[S]] defines a quasi-duality. As a corollary, it is shown that if a ring A has a quasi-duality then the ring A[[S]] of generalized power series over A has a quasi-duality.     

Partially Ordered Monoids Generated by Operators H , S , P , and by H , S , P f Are Isomorphic

Let I , H , S , P , P _f be the usual operators on classes of algebras of the same type (P _f for filtered products). The partially ordered monoid generated by the operators H , S , P with respect to composition of operators, I as an identity element, and a natural ordering between operators is described by Pigozzi (Algebra Universalis 2 (1972), 346—353). Let us denote by \cal M =\langle H, S, P\rangle and by \cal M _f =\langle H, S, P _f \rangle the partially ordered monoids generated by {H, S, P} and by {H, S, P _f } respectively. The aim of this paper is to prove that \cal M is isomorphic to \cal M _f . October 29, 1999     

RADICAL THEORY FOR SEMIRINGS

Abstract

In this article we continue investigations on a Kurosh-Amitsur radical theory for a universal class U of hemirings as introduced by O.M. Olson et al. We give some necessary and sufficient conditions that such a universal class U consists of all hemirings. Further we consider special and weakly special subclasses M of U which yield hereditary radical classes P = um of U. In this context we correct some statements in the papers of Olson et al. Moreover, a problem posed there concerning the equality of two radicals ?_∞(S) and ?^ε(S) and two similar ideals β_∞ (S) and β^ε(S) is widely solved. We prove ?_∞(S) ? ?^ε(S) = β^∞(S) = β^ε(S) and give necessary and sufficient conditions for equality in the first inclusion. This yields in particular that the weakly special class M_ε(U) is always semisimple, a result which is not true for the special class M_∞(U).     

A note on slant submanifolds of nearly trans-Sasakian manifolds

The geometry of slant submanifolds of a nearly trans-Sasakian manifold is studied when the tensor field Q is parallel. It is proved that Q is not parallel on the submanifold unless it is anti-invariant and thus the result of [CABRERIZO, J. L.—CARRIAZO, A.—FERNANDEZ, L. M.—FERNANDEZ, M.: Slant submanifolds in Sasakian manifolds, Glasg. Math. J. 42 (2000), 125–138] and [GUPTA, R. S.—KHURSHEED HAIDER, S. M.—SHARFUDIN, A.: Slant submanifolds of a trans-Sasakian manifold, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 47 (2004), 45–57] are generalized.     

Endomorphism rings and the category of finitely generated projective modules

Given a left R-module M, we study the connection between the (right and left) properties of its endomorphism ring S=End(_RM) and the properties of the category σ _f [M] of all submodules of finitely M-generated left R-modules.     

Vanishing theorem for sheaves of microfunctions at the boundary on cr–manifolds

Let X be a complex analytic manifold. Consider S?M?Xreal analytic submonifolds with codium ^R _MS=1,and let ω be a connected component of M\S. Let p∈S X_MT_M ^*X where T^* _Xdenotes the conormal bundle to M in X, and denote by ν(p) the complex radial Euler field at p. Denote by μ*(Ox) (for * = M, ω) the microlocalization of the sheaf of holomorphic functions along *.

Under the assumption dim^R(T_pT_M ^*X? ν(p)) = 1, a theorem of vanishing for the cohomology groups H^jμM(Ox)p is proved in [K-S 1, Prop. 11.3.1], j being related to the number of positive and negative eigenvalue for the Levi form of M.

Under the hypothesis dim^R(T_pT_S ^*X∩ν(p))=1, a similar result is proved here for the cohomology groups of the complex of microfunctions at the boundary μω(Ox).Stating this result in terms of regularity at the boundary for CR–hyperfunctions a local Bochner–type theorem is then obtained.     

The isotone mappings on Ockham algebras

In this paper we shall describe some algebraic concepts of Ockham algebras. We show that, ifL, M K _1,1 thenH(S(L),S(M)) S(H(L,M)).     

On a continued fraction of order 12

We present some new relations between a continued fraction U(q) of order 12 (established by M. S. M. Naika et al.) and U(q ⁿ ) for n = 7, 9, 11, 13:     

Classification of Möbius Isoparametric Hypersurfaces in ${\Bbb S}^5$

Let M ⁿ be an immersed umbilic-free hypersurface in the (n + 1)-dimensional unit sphere , then M ⁿ is associated with a so-called M?bius metric g, a M?bius second fundamental form B and a M?bius form Φ which are invariants of M ⁿ under the M?bius transformation group of . A classical theorem of M?bius geometry states that M ⁿ (n ≥ 3) is in fact characterized by g and B up to M?bius equivalence. A M?bius isoparametric hypersurface is defined by satisfying two conditions: (1) Φ ≡ 0; (2) All the eigenvalues of B with respect to g are constants. Note that Euclidean isoparametric hypersurfaces are automatically M?bius isoparametrics, whereas the latter are Dupin hypersurfaces. In this paper, we determine all M?bius isoparametric hypersurfaces in by proving the following classification theorem: If is a M?bius isoparametric hypersurface, then x is M?bius equivalent to either (i) a hypersurface having parallel M?bius second fundamental form in ; or (ii) the pre-image of the stereographic projection of the cone in over the Cartan isoparametric hypersurface in with three distinct principal curvatures; or (iii) the Euclidean isoparametric hypersurface with four principal curvatures in . The classification of hypersurfaces in with parallel M?bius second fundamental form has been accomplished in our previous paper [7]. The present result is a counterpart of the classification for Dupin hypersurfaces in up to Lie equivalence obtained by R. Niebergall, T. Cecil and G. R. Jensen. Partially supported by DAAD; TU Berlin; Jiechu grant of Henan, China and SRF for ROCS, SEM. Partially supported by the Zhongdian grant No. 10531090 of NSFC. Partially supported by RFDP, 973 Project and Jiechu grant of NSFC.     

On the convergence of general regularization and smoothing schemes for mathematical programs with complementarity constraints

We extend the convergence analysis of a smoothing method [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg.] to a general class of smoothing functions and show that a weak second-order necessary optimality condition holds at the limit point of a sequence of stationary points found by the smoothing method. We also show that convergence and stability results in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] hold for a relaxation problem suggested by Scholtes [S. Scholtes (2003). Private communications.] using a class of smoothing functions. In addition, the relationship between two technical, yet critical, concepts in [M. Fukushima and J.-S. Pang (2000). Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: M. Théra and R. Tichatschke (Eds.), Ill-posed Variational Problems and Regularization Techniques, pp. 99–110. Springer, Berlin/Heidelberg; S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] for the convergence analysis of the smoothing and regularization methods is discussed and a counter-example is provided to show that the stability result in [S. Scholtes (2001). Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim., 11, 918–936.] cannot be extended to a weaker regularization.     

On the boundedness of solutions of nonlinear differential equations in Hilbert spaces

LetH be a complex Hilbert space and letB be the space of all bounded linear operators fromH intoH with the strong operator topology. We will give a boundedness result for the solutions of the differential equationx′=A(t)x+f(t,x) whereA: I=[t ₀, ∞)→B is continuous,f: I×H→H is also continuous and for every bounded setS⊂I×H there exists a constantM(S)>0 such that |f(t,x)−f(t,y)|≤M(S)|x−y|,(t,x), (t,y)∈S.

---

Sunto SiaH uno spazio di Hilbert complesso e siaB lo spazio degli operatori lineari limitati daH inH, con la topologia forte. In questo lavoro si prova un risultato di limitatezza per le soluzioni dell'equazione differenzialex′=A(t)x+f(t,x), doveA: I=[t ₀, ∞)→B è continua,f: I×H→H è continua e per ogni insieme limitatoS⊂I×H esiste una costanteM(S)>0 tale che |f(t,x)−f(t,y)|≤M(S)|x−y| per ogni(t,x), (t,y)∈S.

     

Equivariant frame fields on spheres with complementary equivariant complex structures

LetG be a finite group and letM be a unitary representation space ofG. We consider the existence problem of equivariant frame fields on the unit sphereS(M) whose orthogonal complements in the tangent bundleT(S(M)) admitG-equivariant complex structures. Under mild fixed point conditions we give a complete solution for this problem whenG is either ℤ/2ℤ or a finite group of odd order. This article was processed by the author using theLaT_EX style filecljourl from Springer-Verlag.     

BOOK REVIEWS

Book reviewed in this article: Physics, A Basic Science, by Elmer E. Burns, Teacher of Physics (Emeritus), Austin High School, Chicago; Frank L. Verwiebe, Associate Professor of Physics, Hamilton College, Research Associate, Army Institute; and Herbert C. Hazel, Major, U. S. Marine Corps. Practical Radio Communication, by Arthur R. Nilson, Chief Instructor, Nilson Radio School, New York, N. Y. Lieutenant (Tecknicist) (Communications) U.S.N.R. (Retired); Member Institute of Radio Engineers, and J. L. Hornung, Lieutenant A-V (R.S) U.S.N.R.; Member Institute of Radio Engineers; Formerly Radio Instructor, New York University. Machines, by Charles R. Wallendorf, Administrative Assistant, Woodrow Wilson Vocational High School, Jamaica, N. Y., Frank Stewart, Department of Applied Physics, Brooklyn Technical High School, N. Y., George Luedeke, Supervisor of Shop Subjects in Vocational High Schools, Board of Education, New York, N. Y., and Dominic M. Chiarello, Department of Applied Electricity, Brooklyn Technical High School, N. Y. Systematics and the Origin of Species, by Ernst Mayr Common Edible Mushrooms, by Clyde M. Christensen Handbook of Microscopic Characteristics of Tissues and Organs, 2nd edition, by Karl A. Stiles Plane Trigonometry, by Arthur W. Weeks, M.A., The Phillips Exeter Academy, and H. Gray Funkhouser, Ph.D. Analytic Geometry, by Frederick H. Steen, Ph.D., Associate Professor of Mathematics, Allegheny College, and Donald H. Ballou, Ph.D., Assistant Professor of Mathematics, Middlebury College. Electricity, by Charles A. Rirsde. Principles and Practice of Radio Servicing, by H. J. Hicks, M.S. Experimental Electronics, by Ralph H. Müller, Professor of Chemistry, New York University; R. L. Carman, Assistant Professor of Chemistry, New York University; and M. E. Droz, Assistant Professor of Chemistry, New York University. Simplified Industrial Mathematics, by John H. Wolfe, Ph.D., Supervisor of Ford Apprentice Training, Ford Motor Company, Dearborn, Michigan; William F. Mueller, A.B., Principal of Ford Aircraft Apprentice School, Ford Motor Company, Dearborn, Michigan; and Seibert D. Mullikin, B.S., Principal of Ford Airplane Apprentice School, Ford Motor Company, Willow Run, Michigan.     

On the homological classification of pomonoids by their Rees factor S-posets

The study of flatness properties of pomonoids acting on posets was initiated by S.M. Fakhruddin in the 1980s. This work has recently been continued by various authors (see references). The Rees factor S-posets are investigated in S. Bulman-Fleming, D. Gutermuth, A. Gilmour and M. Kilp, Flatness properties of  S -posets (Commun. Algebra 34:1291–1317, 2006). In the present article, we investigate the homological classification problems of pomonoids by their Rees factor S-posets. Supported by Research Supervisor Program of Education Department of Gansu Province (0801-03) and nwnu-kjcxgc-03-51.     

On the characterization of p ‐adic Colombeau–Egorov generalized functions by their point values

We show that contrary to recent papers by S. Albeverio, A. Yu. Khrennikov and V. Shelkovich, point values do not determine elements of the so‐called p ‐adic Colombeau–Egorov algebra ??(?ⁿ _p ) uniquely. We further show in a more general way that for an Egorov algebra ??(M, R) of generalized functions on a locally compact ultrametric space (M, d) taking values in a nontrivial ring, a point value characterization holds if and only if (M, d) is discrete. Finally, following an idea due to M. Kunzinger and M. Oberguggenberger, a generalized point value characterization of ??(M, R) is given. Elements of ??(?ⁿ _p ) are constructed which differ from the p ‐adic δ ‐distribution considered as an element of ??(?ⁿ _p ), yet coincide on point values with the latter. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Book Vignettes

Book reviewed in this article: Heavens, O.S., Lasers. Salkind, Charles T. and Earl, James M. (compelers), The MAA Problem Book III: Annual High School Contests of the MAA 1966–1972. Seese, William S., In Preparation for College Chemistry.     

Espaces de Thom et contre-exemples de J.L. Verdier et M. Goresky

Résumé SoitS une variété algébrique complexe singulière, de dimension réelle 2s. M.H. Schwartz et R. Mac-Pherson ont défini des classes caractéristiques, généralisation des classes de Chern, dans l'homologie deS (de telles classes n'existent pas en cohomologie). D'autre part l'homomorphisme de PoincaréH ^2s−⋆ (S)→H _⋆ (S) n'est en géneral, ni injectif, ni surjectif. Cet homomorphisme se factorise par l'homologie d'intersectionIH _⋆ (S). Il est naturel de se demander quel est le “comportement” des classes deS (classes de M.H. Schwartz-R. Mac-Pherson) vis-à-vis du morphisme canonique α:IH _⋆(S)→H_⋆(S). J. L. Verdier a construit un exemple dans lequel, le morphisme canonique α n'étant pas injectif, les classes deS peuvent ètre réalisées de plusieurs manières comme images de classes de Chern de variétés lisses, désingularisations deS, et dont l'homologie est isomorphe àIH _⋆ (S). M. Goresky a construit une variation de cet exemple dans laquelle les classes de Chern ne sont pas dans l'image de α. Nous montrons que ces deux exemples sont cas particuliers d'une même situation:S est un espace de Thom associé à un plongement d'une variétéB dans un espaceIP ^k . L'essentiel de cet article a été écrit lors d'un séjour des auteurs à l'Université du Rio Grande do Sul (Porto-Alegre-Brésil), sur invitation de M. Sebastiani. Nous le remercions ici, ainsi que l'Université de Porto-Alegre, de leur accueil et de leur hospitalité