On the Topology of Real Algebraic Plane Curves

We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position. Previous methods based on the cylindrical algebraic decomposition use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Gröbner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. Our algorithm isolates critical points in boxes and computes a decomposition of the plane by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm demonstrates its efficiency, in particular on high-degree non-generic curves.     

Worm Problem的一个新上界

1966年,Leo Moser提出了一个基本的几何问题,即Worm Problem．该问题是指:在平面上寻找一个面积最小的(凸)区域,使得任何一条长为1的平面曲线都能够通过旋转和平移完全放入该(凸)区域之中．对于要寻找的区域是凸的情形,本文将把目前所知道的最小的上界由0．2738086降低至0．270911861．在最后一部分,我们推广了Worm Problem,并初步给出了一些相应的结果．     

Complexity Lower Bounds for Approximation Algebraic Computation Trees

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.     

An Improved Upper Bound for Leo Moser's Worm Problem

Abstract. A worm ω is a continuous rectifiable arc of unit length in the Cartesian plane. Let W denote the class of all worms. A planar region C is called a cover for W if it contains a copy of every worm in W . That is, C will cover or contain any member ω of W after an appropriate translation and/ or rotation of ω is completed (no reflections). The open problem of determining a cover C of smallest area is attributed to Leo Moser [7], [8]. This paper reduces the smallest known upper bound for this area from 0.275237 [10] to 0.260437.     

An Improved Upper Bound for Leo Moser's Worm Problem

   Abstract. A worm ω is a continuous rectifiable arc of unit length in the Cartesian plane. Let W denote the class of all worms. A planar region C is called a cover for W if it contains a copy of every worm in W . That is, C will cover or contain any member ω of W after an appropriate translation and/ or rotation of ω is completed (no reflections). The open problem of determining a cover C of smallest area is attributed to Leo Moser [7], [8]. This paper reduces the smallest known upper bound for this area from 0.275237 [10] to 0.260437.     

A Divisibility Theorem for the Alexander Polynomial of a Plane Algebraic Curve

An upper estimate for the Alexander polynomial of an algebraic curve is obtained, which sharpens Libgober's estimate in terms of the local polynomials at the singular points of the curve: only those singular points may contribute to the Alexander polynomial of the curve that are in the excess of the hypothesis of Nori's vanishing theorem. Bibliography: 19 titles.     

改进型Hardy-Sobolev不等式最好常数的一个上界

在本文,我们对改进型Hardy-Sobolev不等式的最好常数进行研究,得到该常数的一个上界.     

Topology of Maximally Writhed Real Algebraic Knots

Oleg Viro introduced an invariant of rigid isotopy for real algebraic knots in ??³ which can be viewed as a first order Vassiliev invariant. In this paper we look at real algebraic knots of degree d with the maximal possible value of this invariant. We show that for a given d all such knots are topologically isotopic and explicitly identify their knot type.     

计算平面代数曲线亏格上界的符号-数值算法

亏格是代数曲线的重要不变量.文章给出计算一类平面代数曲线亏格上界的符号-数值混合算法.首先通过数值稳定的符号-数值混合算法把代数曲线的定义多项式系统约化到几何对合形式,然后考察奇点的性质.如果曲线的奇点是寻常的,那么由奇点的重数可以计算出代数曲线的亏格;否则算法仅给出亏格的一个上界.     

Critical Points of Real Polynomials and Topology of Real Algebraic T-Surfaces

The paper is devoted to a special class of real polynomials, so-called T-polynomials, which arise in the combinatorial version of the Viro theorem. We study the relation between the numbers of real critical points of a given index of a T-polynomial and the combinatorics of lattice triangulations of Newton polytopes. We obtain upper bounds for the numbers of extrema and saddles of generic T-polynomials of a given degree in three variables, and derive from them upper bounds for Betti numbers of real algebraic surfaces in defined by T-polynomials. The latter upper bounds are stronger than the known upper bounds for arbitrary real algebraic surfaces in . Another result is the existence of an asymptotically maximal family of real polynomials of degree min three variables with 31m ³/36 + O(m ²) saddle points.     

An Upper Bound for List T-Colourings

Erds, Rubin and Taylor showed in 1979 that for any connectedgraph G which is not a complete graph or an odd cycle, ch(G) , where is the maximum degree of a vertex in G and ch(G) isthe choice number of the graph (also proved by Vizing in 1976).They also gave a characterisation of D-choosability. A graphG is D-choosable if, when we assign to each vertex v of G alist containing d(v) elements, where d(v) is the degree of vertexv, we can always choose a proper vertex colouring from theselists, however the lists were chosen. In this paper we shallgeneralise their results on the choice number of G and D-choosabilityto the case where we have T-colourings.     

Algorithms in Algebraic Topology and Homological Algebra: Problem of Complexity

This review tackles the problem of the high computational complexity lying in most algorithms in algebraic topology and homological algebra. Three particular algorithms are considered: the computation of the homology of commutative differential graded algebras, the homology of principal twisted Cartesian products of EilenbergMacLane spaces, and a combinatorial method of computing Steenrod squares. Bibliography: 54 titles.     

An Upper Bound for the Hyperbolic Metric of a Convex Domain

In [1], Beardon introduced the Apollonian metric defined forany domain D in Rⁿ by This metric is Möbius invariant, and for simply connectedplane domains it satisfies the inequality _D2_D, where _D denotesthe hyperbolic distance in D, and so gives a lower bound onthe hyperbolic distance. Furthermore, it is shown in [1, Theorem6.1] that for convex plane domains, the Apollonian metric satisfies, and, by considering the example of the infinite strip {x + iy:|y|<1}, that the best possibleconstant in this inequality is at least . In this paper we makethe following improvements.     

An Improved Upper Bound on the Linear 2-arboricity of 1-planar Graphs

The linear 2-arboricity la_2(G) of a graph G is the least integer k such that G can be partitioned into k edge-disjoint forests,whose component trees are paths of length at most 2.In this paper,we prove that if G is a 1-planar graph with maximum degree Δ,then la_2(G)≤[(Δ+1)/2]+7.This improves a known result of Liu et al.(2019) that every 1-planar graph G has la_2(G)≤[(Δ+1)/2]+14.We also observe that there exists a 7-regular 1-planar graph G such that la_2(G)=6=[(Δ+1)/2]+2,which implies that our solution is within 6 from optimal.