Minimally separating sets, mediatrices, and Brillouin spaces

Brillouin zones and their boundaries were studied in [J.J.P. Veerman et al., Comm. Math. Phys. 212 (3) (2000) 725] because they play an important role in focal decomposition as first defined by Peixoto in [J. Differential Equations 44 (1982) 271] and in physics [N.W. Ashcroft, N.D. Mermin, Solid State Physics, Holt, Rhinehart, and Winston, 1976; L. Brillouin, Wave Propagation in Periodic Structures, Dover, 1953]. In so-called Brillouin spaces, the boundaries of the Brillouin zones have certain regularity properties which imply that they consist of pieces of mediatrices (or equidistant sets).The purpose of this note is two-fold. First, we give some simple conditions on a metric space which are sufficient for it to be a Brillouin space. These conditions show, for example, that all compact, connected Riemannian manifolds with their usual distance functions are Brillouin spaces. Second, we exhibit a restriction on the Z₂-homology of mediatrices in such manifolds in terms of the Z₂-homology of the manifolds themselves, based on the fact that they are Brillouin spaces. (This will used to obtain a classification up to homeomorphism of surface mediatrices in forthcoming paper [J. Bernhard, J.J.P. Veerman, The topology of surface mediatrices, Portland State University].)     

Validation of Solutions of Construction Problems in Dynamic Geometry Environments

This paper discusses issues concerning the validation of solutions of construction problems in Dynamic Geometry Environments (DGEs) as compared to classic paper-and-pencil Euclidean geometry settings. We begin by comparing the validation criteria usually associated with solutions of construction problems in the two geometry worlds – the ‘drag test’ in DGEs and the use of only straightedge and compass in classic Euclidean geometry. We then demonstrate that the drag test criterion may permit constructions created using measurement tools to be considered valid; however, these constructions prove inconsistent with classical geometry. This inconsistency raises the question of whether dragging is an adequate test of validity, and the issue of measurement versus straightedge-and-compass. Without claiming that the inconsistency between what counts as valid solution of a construction problem in the two geometry worlds is necessarily problematic, we examine what would constitute the analogue of the straightedge-and-compass criterion in the domain of DGEs. Discovery of this analogue would enrich our understanding of DGEs with a mathematical idea that has been the distinguishing feature of Euclidean geometry since its genesis. To advance our goal, we introduce the compatibility criterion, a new but not necessarily superior criterion to the drag test criterion of validation of solutions of construction problems in DGEs. The discussion of the two criteria anatomizes the complexity characteristic of the relationship between DGEs and the paper-and-pencil Euclidean geometry environment, advances our understanding of the notion of geometrical constructions in DGEs, and raises the issue of validation practice maintaining the pace of ever-changing software.     

Cuts, matrix completions and graph rigidity

This paper brings together several topics arising in distinct areas: polyhedral combinatorics, in particular, cut and metric polyhedra; matrix theory and semidefinite programming, in particular, completion problems for positive semidefinite matrices and Euclidean distance matrices; distance geometry and structural topology, in particular, graph realization and rigidity problems. Cuts and metrics provide the unifying theme. Indeed, cuts can be encoded as positive semidefinite matrices (this fact underlies the approximative algorithm for max-cut of Goemans and Williamson) and both positive semidefinite and Euclidean distance matrices yield points of the cut polytope or cone, after applying the functions 1/π arccos(.) or √. When fixing the dimension in the Euclidean distance matrix completion problem, we find the graph realization problem and the related question of unicity of realization, which leads to the question of graph rigidity. Our main objective here is to present in a unified setting a number of results and questions concerning matrix completion, graph realization and rigidity problems. These problems contain indeed very interesting questions relevant to mathematical programming and we believe that research in this area could yield to cross-fertilization between the various fields involved.     

Some remarks on orders of projective planes,planar difference sets and multipliers

In this paper we investigate how finite group theory, number theory, together with the geometry of substructures can be used in the study of finite projective planes. Some remarks concerning the function v(x)= x ² + x + 1are presented, for example, how the geometry of a subplane affects the factorization of v(x). The rest of this paper studies abelian planar difference sets by multipliers.Partially supported by NSA grant MDA904-90-H-1013.     

Borsuk's problem and the chromatic numbers of metric spaces

In this paper, we will give a short survey of various old and new results concerning two closely connected problems of combinatorial geometry - that of K. Borsuk and that of E. Nelson - P. Erdös - H. Hadwiger. We will also present here our very recent achievements on Ramsey numbers.     

Computational geometric aspects of rhythm,melody, and voice-leading

Many problems concerning the theory and technology of rhythm, melody, and voice-leading are fundamentally geometric in nature. It is therefore not surprising that the field of computational geometry can contribute greatly to these problems. The interaction between computational geometry and music yields new insights into the theories of rhythm, melody, and voice-leading, as well as new problems for research in several areas, ranging from mathematics and computer science to music theory, music perception, and musicology. Recent results on the geometric and computational aspects of rhythm, melody, and voice-leading are reviewed, connections to established areas of computer science, mathematics, statistics, computational biology, and crystallography are pointed out, and new open problems are proposed.     

Commuting graphs of boundedly generated semigroups

Araújo, Kinyon and Konieczny (2011) pose several problems concerning the construction of arbitrary commuting graphs of semigroups.We observe that every star-free graph is the commuting graph of some semigroup. Consequently, we suggest modifications for some of the original problems, generalized to the context of families of semigroups with a bounded number of generators, and pose related problems.We construct monomial semigroups with a bounded number of generators, whose commuting graphs have an arbitrary clique number. In contrast to that, we show that the diameter of the commuting graphs of semigroups in a wider class (containing the class of nilpotent semigroups), is bounded by the minimal number of generators plus two.We also address a problem concerning knit degree.     

Local analytic invariants and splitting theorems in differential analysis

We show that several classical problems concerning the splitting of exact sequences of spaces of differentiable functions can be reduced to questions of semicontinuity of discrete local invariants in analytic geometry. We thus provide a uniform approach to the continuous linear solution of the division, composition and extension problems in differential analysis, recovering the classical theorems and giving many new results. Dedicated to the memory of David P. Milman Research partially supported by NSERC operating grant A9070. Supported by NSERC University Research Fellowship and operating grant A8849.     

Geometry Optimization of Branched Sheet Metal Products

Geometry Optimization plays an important role concerning to design tasks in mechanical engineering. For those we are studying sheet metal products like cable conduits. We formulate a nonlinear, continuous optimization problem to find an optimal geometry for such a sheet metal product. The goal is to find from a given topology the optimal geometry parameters concerning to the minimal bending of a cable conduit, spanning a huge distance. Hereby a lot of constraints, like given sizes of cross-section areas of the chambers, given quantity of sheet metal, and so on have to be fullfilled. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On a series of problems related to the Borsuk and Nelson-Erdős-Hadwiger problems

In the present paper, a series of problems connecting the Borsuk and Nelson-Erd?s-Hadwiger classical problems in combinatorial geometry is considered. The problem has to do with finding the number χ(n, a, d) equal to the minimal number of colors needed to color an arbitrary set of diameter d in n-dimensional Euclidean space in such a way that the distance between points of the same color cannot be equal to a. Some new lower bounds for the quantity χ(n, a, d) are obtained.     

Scanline algorithms on a grid

A number of important problems in computational geometry are solved efficiently on 2- or 3-dimensional grids by means of scanline techniques. In the time complexity of solutions to the maximal elements and closure problems, a factor logn is substituted by loglogn, wheren is the number of elements. Next, by using a data structure introduced in the paper, the interval trie, previous solutions to the rectangle intersection and connected component problems are improved upon. Finally, a fast intersection finding algorithm for arbitrarily oriented line segments is presented.     

Combinatorial Veronese Structures, Their Geometry, and Problems of Embeddability

Finite generalized Veronese spaces of special type (associated with single-line geometry) are studied, and problems concerning embeddability of the resulting configurations are discussed. Received: October 17, 2005. Revised: February 13, 2006.     

Dragging as a conceptual tool in dynamic geometry environments

Some ‘drag-to-fit’ solutions given by student teachers to three geometric construction problems in a dynamic geometry environment (DGE) are analysed. The responses of a group of experienced mathematics teachers to the question whether or not such solutions can be considered ‘legitimate’ are then discussed. This raises fundamental questions concerning the concept of legitimacy, the relationship between DGEs and Formal Axiomatic Euclidean Geometry, the nature of ‘conceptual tools’ in different geometric environments, and the functions of dragging in DGEs. The authors argue that, if dragging is viewed as a conceptual tool, then certain drag-to-fit solutions, although soft constructions, may still be considered as conceptually legitimate and therefore valid. Finally, some important questions are raised concerning the impact that teachers’ different attitudes towards legitimacy might have on students’ learning through DGEs.     

Error analysis and preconditioning for an enhanced DtN-FE algorithm for exterior scattering problems

In this paper we present an error analysis for a high-order accurate combined Dirichlet-to-Neumann (DtN) map/finite element (FE) algorithm for solving two-dimensional exterior scattering problems. We advocate the use of an exact DtN (or Steklov–Poincaré) map at an artificial boundary exterior to the scatterer to truncate the unbounded computational region. The advantage of using an exact DtN map is that it provides a transparent condition which does not reflect scattered waves unphysically. Our algorithm allows for the specification of quite general artificial boundaries which are perturbations of a circle. To compute the DtN map on such a geometry we utilize a boundary perturbation method based upon recent theoretical work concerning the analyticity of the DtN map. We also present some preliminary work concerning the preconditioning of the resulting system of linear equations, including numerical experiments.     

Multipole methods for boundary-value problems involving a sphere in a tube

It is shown how the same mathematical technique can be usedto solve a number of different problems all concerned with thesame geometry. The multipole method, which can be thought ofas an extension of separation of variables to problems wherethe boundaries lie on the coordinate surfaces of two differentcoordinate systems, is used to solve the problems of potentialflow, Stokes flow, and acoustic scattering for the case of asphere situated on the axis of a circular cylindrical tube.     

Grid construction for discretely defined configurations

An important element of global software codes for computing real-life three-dimensional problems with singularities (such as boundary and internal layers, shocks, detonation waves, combustion fronts, high-speed jets, and phase transition zones) is automatic adaptive grid generation, which can considerably enhance the efficiency of computer resource management. In three-dimensional domains with boundaries of complex geometry, in particular, with discretely defined boundaries, adaptive grids are generated by applying inverted Beltrami and diffusion equations for a spherical monitor tensor.     

Steric hindrance effects in thin reaction zones: applications to BIAcore

Many biological and industrial processes have reactions whichoccur in thin zones of densely packed receptors. Understandingthe rate of such reactions is important, and the BIAcore surfaceplasmon resonance biosensor for measuring rate constants hassuch a geometry. However, interpreting biosensor data correctlyis difficult since large ligand molecules can block multiplereceptor sites, thus skewing the kinetics. General mathematicalprinciples are presented for handling this phenomenon, and areceptor layer model is presented explicitly. An integro-partialdifferential equation results. Using perturbation techniques,the problem can be simplified somewhat. In the limit of smallDamköhler number, the non-local nature of the system becomesevident in the association problem, while other experimentscan be modelled using local techniques. Explicit and asymptoticsolutions are constructed for large-molecule cases motivatedby experimental design. The analysis provides insight into surface–volumereactions occurring in various contexts. In particular, thissteric hindrance effect can often be quantified with a singledimensionless parameter.     

Transversals of d-Intervals

We present a method which reduces a family of problems in combinatorial geometry (concerning multiple intervals) to purely combinatorial questions about hypergraphs. The main tool is the Borsuk—Ulam theorem together with one of its extensions. For a positive integer d, a homogeneous d-interval is a union of at most d closed intervals on a fixed line ℓ. Let be a system of homogeneous d-intervals such that no k + 1 of its members are pairwise disjoint. It has been known that its transversal number can then be bounded in terms of k and d. Tardos [9] proved that for d = 2, one has . In particular, the bound is linear in k. We show that the latter holds for any d, and prove the tight bound for d = 2. We obtain similar results in the case of nonhomogeneous d-intervals whose definition appears below. Received June 10, 1995, and in revised form June 13, 1996.     

An Adaptive Subdivision Algorithm for the Identification of the Diffusion Coefficient in Two-dimensional Elliptic Problems

In this work, we consider the identification problem of the diffusion coef-ficient in two-dimensional elliptic equations. For parameterization, we use the zonation method: the diffusion coefficient is assumed to be a piecewise constant space function and unknowns are both the diffusion coefficient values and the geometry of the zones. An algorithm based on geometric principles is developed in order to determine the boundaries between the zones. This algorithm uses the refinement indicators which are easily computed from the gradient of the objective function. The efficiency of the algorithm is proved by testing it in some simple cases with and without noise on the data.      

A note concerning reduced algebraic numbers and equivalence of binary forms

In an earlier paper (J. Wolfskill, J. Number Theory 16 (1983), 205–211) a method was given to determine whether or not two binary forms are equivalent by examining the corresponding problem for the roots. The latter problem was solved, in the case that each form has a real root, by applying the theory of reduced algebraic numbers. However, there are two important problems remaining to be resolved concerning the effectiveness of this method. The first is to show that a given real algebraic number reduces in a bounded (effectively computable) number of steps. The second is to determine under what conditions a form of even degree can be equivalent to its negative. These two problems are solved in this paper.