Characterization and algorithms of curve map graphs

A curve map is a planar map obtained by dividing the Euclidean plane into a finite number of regions by a finite set of two-way infinite Jordan curves (every one dividing the plane in two regions) such that no two curves intersect in more than one point. A line map is a curve map obtained by Jordan curves being all straight lines. A graph is called a curve map graph respectively a line map graph if it is the dual of a curve map respectively of a line map.In this paper we give a characterization of the curve map graphs and we describe a polynomial time algorithm for their recognition.     

On a special case of the intersection of quadric and cubic surfaces

The intersection curve between two surfaces in three-dimensional real projective space RP³ is important in the study of computer graphics and solid modelling. However, much of the past work has been directed towards the intersection of two quadric surfaces. In this paper we study the intersection curve between a quadric and a cubic surface and its projection onto the plane at infinity. Formulas for the plane and space curves are given for the intersection of a quadric and a cubic surface. A family of cubic surfaces that give the same space curve when we intersect them with a quadric surface is found. By generalizing the methods in Wang et al. (2002) [6] that are used to parametrize the space curve between two quadric surfaces, we give a parametrization for the intersection curve between a quadric and a cubic surface when the intersection has a singularity of order 3.     

Breaking hyperbolicity for smooth symplectic toral diffeomorphisms

We study a smooth symplectic 2-parameter unfolding of an almost hyperbolic diffeomorphism on two-dimensional torus. This diffeomorphism has a fixed point of the type of the degenerate saddle. In the parameter plane there is a bifurcation curve corresponding to the transition from the degenerate saddle into a saddle and parabolic fixed point, separatrices of these latter points form a channel on the torus. We prove that a saddle period-2 point exists for all parameter values close to the co-dimension two point whose separatrices intersect transversely the boundary curves of the channel that implies the existence of a quadratic homoclinic tangency for this period-2 point which occurs along a sequence of parameter values accumulating at the co-dimension 2 point. This leads to the break of stable/unstable foliations existing for almost hyperbolic diffeomorphism. Using the results of Franks [1] on π ₁-diffeomorphisms, we discuss the possibility to get an invariant Cantor set of a positive measure being non-uniformly hyperbolic.     

Topological conjugacy of linear endomorphisms of the 2-torus

We describe two complete sets of numerical invariants of topological conjugacy for linear endomorphisms of the two-dimensional torus, i.e., continuous maps from the torus to itself which are covered by linear maps of the plane. The trace and determinant are part of both complete sets, and two candidates are proposed for a third (and last) invariant which, in both cases, can be understood from the topological point of view. One of our invariants is in fact the ideal class of the Latimer-MacDuffee-Taussky theory, reformulated in more elementary terms and interpreted as describing some topology. Merely, one has to look at how closed curves on the torus intersect their image under the endomorphism. Part of the intersection information (the intersection number counted with multiplicity) can be captured by a binary quadratic form associated to the map, so that we can use the classical theories initiated by Lagrange and Gauss. To go beyond the intersection number, and shortcut the classification theory for quadratic forms, we use the rotation number of Poincaré.

     

Stable maps from surfaces to the plane with prescribed branching data

We consider the problem of constructing stable maps from surfaces to the plane with branch set a given set of curves immersed (except possibly with cusps) in the plane. Various constructions are used (1) piecing together regions immersed in the plane (2) modifying an existing stable map by a sequence of codimension one transitions (swallowtails etc) or by surgeries. In (1) the way the regions are pieced together is described by a bipartite graph (an edge C* corresponds to a branch curve C with the vertices of C* corresponding to the two regions containing C). We show that any bipartite graph may be realized by a stable map and we consider the question of realizing graphs by fold maps (i.e. maps without cusps). For example, using Arnol'd's classification of immersed curves, we list all branch sets with at most two branch curves and four double points realizable by planar fold maps of the torus.     

Intersection graphs of curves in the plane

Let V be a set of curves in the plane. The corresponding intersection graph has V as the set of vertices, and two vertices are connected by an edge if and only if the two corresponding curves intersect in the plane.It is shown that the set of intersection graphs of curves in the plane is a proper subset of the set of all undirected graphs. Furthermore, the set of intersection graphs of straight line-segments is a proper subset of the set of the intersection graphs of curves in the plane. Finally, it is shown that for every k ≥ 3, the problem of determining whether an intersection graph of straight line-segments is k-colorable is NP-complete.     

二阶曲线间的射影映射

平面上的射影变换,将二阶曲线变为另一二阶曲线,这个射影变换也可以称为这两个二阶曲线间的射影映射.若两个二阶曲线相切,则存在以切点为射影中心的两个二阶曲线间的射影映射;若两个二阶曲线相离,则存在以两个二阶曲线公切线交点为射影中心的射影映射;若两个二阶曲线相交,则存在以其中一交点为射影中心的两个二阶曲线间的射影映射.     

Triangle Contact Representations and Duality

A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.     

On the edge-coloring problem for a class of 4-regular maps

A (plane) 4-regular map G is called C-simple if it arises as a superposition of simple closed curves (tangencies are not allowed); in this case σ (G) is the smallest integer k such that the curves of G can be colored with k colors in such a way that no two curves of the same color intersect. We prove that if σ (G) ≤ 4, G is edge colorable with 4 colors. Moreover we show that a similar result for maps G with σ(G) ≤ 5 would imply the Four-Color Theorem.     

On multiplicity of intersection point of two plane algebraic curves

The paper studies the multiplicity of intersecting point of two plane algebraic curves. The multiplicity is characterized by means of operators with partial derivatives. It is proved that if A is a point of multiplicity m for one of the curves and, a point of multiplicity n for the other curve, then the arithmetical multiplicity of the intersection (or the number of intersections) of the curves in A, is not less than mn and is equal to mn when the curves do not have common tangents at the point A.     

A two-parameter spectral theorem

Summary We study the characteristic set of a couple (A, B) of selfadjoint compact operators on a real Hilbert spaceH. We prove thatC is the union of a sequence of characteristic curvesC _n in the (, ) plane. Each curve is the analytic image of an open interval and it is either closed or it goes to infinity at both ends of the interval. Moreover, it may intersect either itself or other characteristic curves in an at most countable set of points, which may accumulate only at infinity. Finally, to each characteristic curve one can associate an analytic function E_n, which gives the eigenprojection onto the eigenspace attached to each point of the characteristic curve, except at the intersection points, where the eigenspace is the direct sum of the projection relevant to each branch passing through the point. The dimension of the eigenprojection is constant along each curve and it is called the multiplicity of the characteristic curve.     

First order hermite interpolation with spherical Pythagorean-hodograph curves

The general stereographic projection which maps a point on a sphere with arbitrary radius to a point on a plane stereographically and its inverse projection have the Pythagorean-hodograph (PH) preserving property in the sense that they map a PH curve to another PH curve. Upon this fact, for given spatialC ¹ Hermite data, we construct a spatial PH curve on a sphere that is aC ¹ Hermite interpolant of the given data as follows: First, we solveC ¹ Hermite interpolation problem for the stereographically projected planar data of the given data in ?³ with planar PH curves expressed in the complex representation. Second, we construct spherical PH curves which are interpolants for the given data in ?³ using the inverse general stereographic projection.     

Nonuniqueness for Willmore Surfaces of Revolution Satisfying Dirichlet Boundary Data

In this note Willmore surfaces of revolution with Dirichlet boundary conditions are considered. We show two nonuniqueness results by reformulating the problem in the hyperbolic half plane and solving a suitable initial value problem for the corresponding elastic curves. The behavior of such elastic curves is examined by a method provided by Langer and Singer to reduce the order of the underlying ordinary differential equation. This ensures that these solutions differ from solutions already obtained by Dall’Acqua, Deckelnick and Grunau. We will additionally provide a Bernstein-type result concerning the profile curve of a Willmore surface of revolution. If this curve is a graph on the whole real numbers it has to be a Möbius transformed catenary. We show this by a corollary of the above-mentioned method by Langer and Singer.     

Commuting dual billiard maps

To a closed convex smooth curve in the plane the dual billiard transformation of its exterior corresponds: given a point outside of the curve, draw a tangent line to it through the point, and reflect the point in the point of tangency. We prove that if two curves are given, such that the corresponding dual billiard transformations commute, then the curves are concentric homothetic ellipses.     

Box-counting by Hölder’s traveling salesman

We provide a sufficient Dini-type condition for a subset of a complete, quasiconvex metric space to be covered by a Hölder curve. This implies in particular that if the upper box-counting dimension is less than $$d \ge 1$$, then it can be covered by an $$\frac{1}{d}$$-Hölder curve. On the other hand, for each $$1\le d <2$$ we give an example of a compact set in the plane with lower box-counting dimension equal to zero and upper box-counting dimension equal to d, just failing the above Dini-type condition, that can not be covered by a countable collection of $$\frac{1}{d}$$-Hölder curves.     

Continuous Subsonic-Sonic Flows in a Convergent Nozzle

This paper concerns continuous subsonic-sonic potential flows in a two-dimensional convergent nozzle. It is shown that for a given nozzle which is a perturbation of a straight one, a given point on its wall where the curvature is zero, and a given inlet which is a perturbation of an arc centered at the vertex, there exists uniquely a continuous subsonic-sonic flow whose velocity vector is along the normal direction at the inlet and the sonic curve, which satisfies the slip conditions on the nozzle walls and whose sonic curve intersects the upper wall at the given point. Furthermore, the sonic curve of this flow is a free boundary, where the flow is singular in the sense that the speed is only C^1/2 Hölder continuous and the acceleration blows up. The perturbation problem is solved in the potential plane, where the flow is governed by a free boundary problem of a degenerate elliptic equation with two free boundaries and two nonlocal boundary conditions, and the equation is degenerate at one free boundary.     

Onk-sets in arrangements of curves and surfaces

We extend the notion ofk-sets and (≤k)-sets (see [3], [12], and [19]) to arrangements of curves and surfaces. In the case of curves in the plane, we assume that each curve is simple and separates the plane. Ak-point is an intersection point of a pair of the curves which is covered by exactlyk interiors of (or half-planes bounded by) other curves; thek-set is the set of allk-points in such an arrangement, and the (≤k)-set is the union of allj-sets, forj≤k. Adapting the probabilistic analysis technique of Clarkson and Shor [13], we obtain bounds that relate the maximum size of the (≤k)-set to the maximum size of a 0-set of a sample of the curves. Using known bounds on the size of such 0-sets we obtain asympotically tight bounds for the maximum size of the (≤k)-set in the following special cases: (i) If each pair of curves intersect at most twice, the maximum size is Θ(nkα(nk)). (ii) If the curves are unbounded arcs and each pair of them intersect at most three times, then the maximum size is Θ(nkα(n/k)). (iii) If the curves arex-monotone arcs and each pair of them intersect in at most some fixed numbers of points, then the maximum size of the (≤k)-set is Θ(k ²λ _s (nk)), where λ _s (m) is the maximum length of (m,s)-Davenport-Schinzel sequences. We also obtain generalizations of these results to certain classes of surfaces in three and higher dimensions. Finally, we present various applications of these results to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more. An interesting application yields andO(n logn) bound on the expected number of vertically visible features in an arrangement ofn horizontal discs when they are stacked on top of each other in random order. This in turn leads to an efficient randomized preprocessing ofn discs in the plane so as to allow fast stabbing queries, in which we want to report all discs containing a query point. Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the NCRD—the Israeli National Council for Research and Development-and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Curves on the shape sphere

Using a special conformai map between the two-dimensional sphere and the extended plane, we describe some classes of curves on the sphere. We also discuss a differential geometric invariant determining a plane curve up to a direct similarity and study self-similar plane curves.     

Notes on pedal and contrapedal curves of fronts in the Euclidean plane

A pedal curve (a contrapedal curve) of a regular plane curve is the locus of the feet of the perpendiculars from a point to the tangents (normals) to the curve. These curves can be parametrized by using the Frenet frame of the curve. Yet provided that the curve has some singular points, the Frenet frame at these singular points is not well‐defined. Thus, we cannot use the Frenet frame to examine pedal or contrapedal curves. In this paper, pedal and contrapedal curves of plane curves, which have singular points, are investigated. By using the Legendrian Frenet frame along a front, the pedal and contrapedal curves of a front are introduced and properties of these curves are given. Then, the condition for a pedal (and a contrapedal) curve of a front to be a frontal is obtained. Furthermore, by considering the definitions of the evolute, the involute, and the offset of a front, some relationships are given. Finally, some illustrated examples are presented.     

Twelve points on the projective line, branched covers, and rational elliptic fibrations

The following divisors in the space of twelve points on are actually the same: the possible locus of the twelve nodal fibers in a rational elliptic fibration (i.e. a pencil of plane cubic curves); degree 12 binary forms that can be expressed as a cube plus a square; the locus of the twelve tangents to a smooth plane quartic from a general point of the plane; the branch locus of a degree 4 map from a hyperelliptic genus 3 curve to ; the branch locus of a degree 3 map from a genus 4 curve to induced by a theta-characteristic; and several more. The corresponding moduli spaces are smooth, but they are not all isomorphic; some are finite étale covers of others. We describe the web of interconnections among these spaces, and give monodromy, rationality, and Prym-related consequences. Enumerative consequences include: (i) the degree of this locus is 3762 (e.g. there are 3762 rational elliptic fibrations with nodes above 11 given general points of the base); (ii) if is a cover as in , then there are 135 different such covers branched at the same points; (iii) the general set of 12 tangent lines that arise in turn up in 120 essentially different ways. Some parts of this story are well known, and some other parts were known classically (to Zeuthen, Zariski, Coble, Mumford, and others). The unified picture is surprisingly intricate and connects many beautiful constructions, including Recillas' trigonal construction and Shioda's -Mordell-Weil lattice. Received November 3, 1999 / Published online February 5, 2001