School of Mathematics and Statistics - Research Publications

Permanent URI for this collection

Search Results

Now showing 1 - 10 of 19
  • Item
    No Preview Available
    SPUN NORMAL SURFACES IN 3-MANIFOLDS III: BOUNDARY SLOPES
    Kang, E ; Rubinstein, JH (American Mathematical Society (AMS), 2022-09-01)

    Spun normal surfaces are a useful way of representing proper essential surfaces, using ideal triangulations for 3-manifolds with tori and Klein bottle boundaries. In this paper, we consider spinning essential surfaces in an irreducibleP2P^2-irreducible, anannular, atoroidal 3-manifold with tori and Klein bottle boundary components. We can assume that such a 3-manifold is equipped with an ideal 1-efficient triangulation. In particular, we prove that for a given choice of a set of boundary slopes for a proper essential surface, there is a set of essential vertex solutions for the projective solution space at these boundary slopes, answering a question of Dunfield and Garoufalidis [Trans. Amer. Math. Soc. 364 (2012), pp. 6109–6137], so long as the slopes are not of a fiber of a bundle structure.

  • Item
    No Preview Available
    Counting essential surfaces in 3-manifolds
    Dunfield, NM ; Garoufalidis, S ; Rubinstein, JH (SPRINGER HEIDELBERG, 2022-05)
  • Item
    Thumbnail Image
    Minimum Steiner trees on a set of concyclic points and their center
    Whittle, D ; Brazil, M ; Grossman, PA ; Rubinstein, JH ; Thomas, DA (WILEY, 2022-07)
    Abstract Consider a configuration of points comprising a point q and a set of concyclic points R that are all a given distance r from q in the Euclidean plane. In this paper, we investigate the relationship between the length of a minimum Steiner tree (MStT) on and a minimum spanning tree on R. We show that if the degree of q in the MStT is 1, then the difference between these two lengths is at least , and that this lower bound is tight. This bound can be applied as part of an efficient algorithm to find the solution to the prize‐collecting Euclidean Steiner tree problem, as outlined in an earlier paper.
  • Item
    Thumbnail Image
    Curvature-constrained directional-cost paths in the plane
    Chang, AJ ; Brazil, M ; Rubinstein, JH ; Thomas, DA (SPRINGER, 2012-08)
  • Item
    Thumbnail Image
    Gradient-Constrained Minimum Networks. III. Fixed Topology
    Brazil, M ; Rubinstein, JH ; Thomas, DA ; Weng, JF ; Wormald, N (SPRINGER/PLENUM PUBLISHERS, 2012-10)
  • Item
    Thumbnail Image
    Maximizing the net present value of a Steiner tree
    Sirinanda, KG ; Brazil, M ; Grossman, PA ; Rubinstein, JH ; Thomas, DA (Springer US, 2015)
    The theory of Steiner trees has been extensively applied in physical network design problems to locate a Steiner point that minimizes the total length of a tree. However, maximizing the total generated cash flows of a tree has not been investigated. Such a tree has costs associated with its edges and values associated with nodes. In order to reach the nodes in the tree, the edges need to be constructed. The edges are constructed in a particular order and the costs of constructing the edges and the values at the nodes are discounted over time. These discounted costs and values generate cash flows. In this paper, we study the problem of optimally locating a single Steiner point so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An application of this problem occurs in underground mining where, we want to optimally locate a junction point in the underground access network to maximize the NPV. We propose an efficient iterative algorithm to optimally locate a single degree-3 Steiner point. We show this algorithm converges quickly and the Steiner point is unique subject to realistic design parameters.
  • Item
    Thumbnail Image
    Optimal curvature-constrained paths for general directional-cost functions
    Chang, AJ ; Brazil, M ; Rubinstein, JH ; Thomas, DA (SPRINGER, 2013-09)
  • Item
    Thumbnail Image
    Z2-Thurston norm and complexity of 3-manifolds
    Jaco, W ; Rubinstein, JH ; Tillmann, S (SPRINGER HEIDELBERG, 2013-05)
  • Item
    Thumbnail Image
    Solving the prize-collecting Euclidean Steiner tree problem
    Whittle, D ; Brazil, M ; Grossman, PA ; Rubinstein, JH ; Thomas, DA (WILEY, 2022-05)
    Abstract The prize‐collecting Euclidean Steiner tree (PCEST) problem is a generalization of the well‐known Euclidean Steiner tree (EST) problem. All points given in an EST problem instance are connected by the shortest possible network in a solution. A solution can include additional points called Steiner points. A PCEST problem instance differs from an EST problem instance by the addition of weights for each given point. A PCEST solution connects a subset of the given points in order to maximize the net value of the network (the sum of the selected point weights, less than the length of the network). We present an algorithmic framework for solving the PCEST problem. Included in the framework are efficient methods to determine subsets of points that must be in every solution, and subsets of points that cannot be in any solution. Also included are methods to generate and concatenate full Steiner trees.
  • Item
    No Preview Available
    Optimal curvature and gradient-constrained directional cost paths in 3-space
    Chang, AJ ; BRAZIL, M ; Rubinstein, JH ; Thomas, DA (Springer Verlag, 2015-07-01)