skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Reconstruction of the Crossing Type of a Point Set from the Compatible Exchange Graph of Noncrossing Spanning Trees
Let P be a set of n points in the plane in general position. The order type of P specifies, for every ordered triple, a positive or negative orientation; and the x-type (a.k.a. crossing type) of P specifies, for every unordered 4-tuple, whether they are in convex position. Geometric algorithms on P typically rely on primitives involving the order type or x-type (i.e., triples or 4-tuples). In this paper, we show that the x-type of P can be reconstructed from the compatible exchange graph G1(P) of noncrossing spanning trees on P. This extends a recent result by Keller and Perles (2016), who proved that the x-type of P can be reconstructed from the exchange graph G0(P) of noncrossing spanning trees, where G1(P) is a subgraph of G0(P) . A crucial ingredient of our proof is a structure theorem on the maximal sets of pairwise noncrossing edges (msnes) between two components of a planar straight-line graph on the point set P.  more » « less
Award ID(s):
1423615
PAR ID:
10097780
Author(s) / Creator(s):
Date Published:
Journal Name:
International Conference on Discrete Geometry for Computer Imagery
Volume:
11414
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Felsner, Stefan; Klein, Karsten (Ed.)
    Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing. 
    more » « less
  2. ; ; ; ; ; (, Journal of General Physiology)
    The force response of cardiac muscle undergoing a quick stretch is conventionally interpreted to represent stretching of attached myosin crossbridges (phase 1) and detachment of these stretched crossbridges at an exponential rate (phase 2), followed by crossbridges reattaching in increased numbers due to an enhanced activation of the thin filament (phases 3 and 4). We propose that, at least in mammalian cardiac muscle, phase 2 instead represents an enhanced detachment rate of myosin crossbridges due to stretch, phase 3 represents the reattachment of those same crossbridges, and phase 4 is a passive-like viscoelastic response with power-law relaxation. To test this idea, we developed a two-state model of crossbridge attachment and detachment. Unitary force was assigned when a crossbridge was attached, and an elastic force was generated when an attached crossbridge was displaced. Attachment rate, f(x), was spatially distributed with a total magnitude f0. Detachment rate was modeled as g(x) = g0+ g1x, where g0 is a constant and g1 indicates sensitivity to displacement. The analytical solution suggested that the exponential decay rate of phase 2 represents (f0 + g0) and the exponential rise rate of phase 3 represents g0. The depth of the nadir between phases 2 and 3 is proportional to g1. We prepared skinned mouse myocardium and applied a 1% stretch under varying concentrations of inorganic phosphate (Pi). The resulting force responses fitted the analytical solution well. The interpretations of phases 2 and 3 were consistent with lower f0 and higher g0 with increasing Pi. This novel scheme of interpreting the force response to a quick stretch does not require enhanced thin-filament activation and suggests that the myosin detachment rate is sensitive to stretch. Furthermore, the enhanced detachment rate is likely not due to the typical detachment mechanism following MgATP binding, but rather before MgADP release, and may involve reversal of the myosin power stroke. 
    more » « less
  3. ; ; ; ; ; (, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)
    Mestre, Julián; Wirth, Anthony (Ed.)
    For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case. 
    more » « less
  4. ; (, ICML 2023)
    We make a connection between multicalibration and property elicitation and show that (under mild technical conditions) it is possible to produce a multicalibrated predictor for a continuous scalar distributional property G if and only if G is elicitable. On the negative side, we show that for non-elicitable continuous properties there exist simple data distributions on which even the true distributional predictor is not calibrated. On the positive side, for elicitable G, we give simple canonical algorithms for the batch and the online adversarial setting, that learn a G-multicalibrated predictor. This generalizes past work on multicalibrated means and quantiles, and in fact strengthens existing online quantile multicalibration results. To further counter-weigh our negative result, we show that if a property G1 is not elicitable by itself, but is elicitable conditionally on another elicitable property G0, then there is a canonical algorithm that jointly multicalibrates G1 and G0; this generalizes past work on mean-moment multicalibration. Finally, as applications of our theory, we provide novel algorithmic and impossibility results for fair (multicalibrated) risk assessment. 
    more » « less
  5. ; ; ; ; (, Annals of Combinatorics)
    An equidistant X-cactus is a type of rooted, arc-weighted, directed acyclic graph with leaf set X, that is used in biology to represent the evolutionary history of a set X of species. In this paper, we introduce and investigate the space of equidistant X-cactuses. This space contains, as a subset, the space of ultrametric trees on X that was introduced by Gavryushkin and Drummond. We show that equidistant-cactus space is a CAT(0)-metric space which implies, for example, that there are unique geodesic paths between points. As a key step to proving this, we present a combinatorial result concerning ranked rooted X-cactuses. In particular, we show that such graphs can be encoded in terms of a pairwise compatibility condition arising from a poset of collections of pairs of sub- sets of X that satisfy certain set-theoretic properties. As a corollary, we also obtain an encoding of ranked, rooted X-trees in terms of partitions of X, which provides an alternative proof that the space of ultrametric trees on X is CAT(0). We expect that our results will provide the basis for novel ways to perform statistical analyses on collections of equidistant X-cactuses, as well as new directions for defining and understanding spaces of more general, arc-weighted phylogenetic networks. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email