260 research outputs found
Computing the Fréchet Gap Distance
No full textMeasuring the similarity of two polygonal curves is a fundamental computational task. Among alternatives, the Frechet distance is one of the most well studied similarity measures. Informally, the Fréchet distance is described as the minimum leash length required for a man on one of the curves to walk a dog on the other curve continuously from the starting to the ending points. In this paper we study a variant called the Fréchet gap distance. In the man and dog analogy, the Fréchet gap distance minimizes the difference of the longest and smallest leash lengths used over the entire walk. This measure in some ways better captures our intuitive notions of curve similarity, for example giving distance zero to translated copies of the same curve.
The Fréchet gap distance was originally introduced by Filtser and Katz (2015) in the context of the discrete Fréchet distance. Here we study the continuous version, which presents a number of additional challenges not present in discrete case. In particular, the continuous nature makes bounding and searching over the critical events a rather difficult task.
For this problem we give an O(n^5 log(n)) time exact algorithm and a more efficient O(n^2 log(n) + (n^2/epsilon) log(1/epsilon)) time (1+epsilon)-approximation algorithm, where n is the total number of vertices of the input curves. Note that for (small enough) constant epsilon and ignoring logarithmic factors, our approximation has quadratic running time, matching the lower bound, assuming SETH (Bringmann 2014), for approximating the standard Fréchet distance for general curves
Linear Expected Complexity for Directional and Multiplicative Voronoi Diagrams
No full textWhile the standard unweighted Voronoi diagram in the plane has linear worst-case complexity, many of its natural generalizations do not. This paper considers two such previously studied generalizations, namely multiplicative and semi Voronoi diagrams. These diagrams both have quadratic worst-case complexity, though here we show that their expected complexity is linear for certain natural randomized inputs. Specifically, we argue that the expected complexity is linear for: (1) semi Voronoi diagrams when the visible direction is randomly sampled, and (2) for multiplicative diagrams when either weights are sampled from a constant-sized set, or the more challenging case when weights are arbitrary but locations are sampled from a square
Generalized Metric Repair on Graphs
No full textMany modern data analysis algorithms either assume or are considerably more efficient if the distances between the data points satisfy a metric. However, as real data sets are noisy, they often do not possess this fundamental property. For this reason, Gilbert and Jain [A. Gilbert and L. Jain, 2017] and Fan et al. [C. Fan et al., 2018] introduced the closely related sparse metric repair and metric violation distance problems. Given a matrix, representing all distances, the goal is to repair as few entries as possible to ensure they satisfy a metric. This problem was shown to be APX-hard, and an O(OPT^{1/3})-approximation was given, where OPT is the optimal solution size.
In this paper, we generalize the problem, by describing distances by a possibly incomplete positively weighted graph, where again our goal is to find the smallest number of weight modifications so that they satisfy a metric. This natural generalization is more flexible as it takes into account different relationships among the data points. We demonstrate the inherent combinatorial structure of the problem, and give an approximation-preserving reduction from MULTICUT, which is hard to approximate within any constant factor assuming UGC. Conversely, we show that for any fixed constant ς, for the large class of ς-chordal graphs, the problem is fixed parameter tractable, answering an open question from previous work. Call a cycle broken if it contains an edge whose weight is larger than the sum of all its other edges, and call the amount of this difference its deficit. We present approximation algorithms, one depending on the maximum number of edges in a broken cycle, and one depending on the number of distinct deficit values, both quantities which may naturally be small. Finally, we give improved analysis of previous algorithms for complete graphs
Nano-self-assembly in Mn-based spinels through solid state process
No full textTransition-metal oxides characterized with anisotropic d-orbital electrons are subject to intense discussion in strongly correlated electron systems, ranging from colossal magnetoresistance (CMR) to high temperature superconductivity (HTSC). The orbital degree of freedom often underpins complex physical properties and a variety of extraordinary phenomena while coupling with charge, spin and lattice. In this thesis, we demonstrate a fascinating example of orbital-related physical properties in Mn-based spinels. The strong octahedral preference of Jahn-Teller ions Mn3+ results in simultaneous chemical and structural phase separation into Mn-poor (cubic) and Mn-rich (tetragonal) regions, forming two types of rectangular nanorods with cross section checkerboard-like (CB). Because of the pioneering discovery of checkerboards in the nonmagnetic ZnMnxGa1-xO4, we chose to study two magnetic spinel systems: (1) Mg(MnxFe1-x)O4, where unfortunately only poorly-ordered magnetic nano CBs were observed; and (2) Mn-doped CoFe2O4, the nano CBs with distinct magnetic properties and tunable sizes achieved here are highly ordered, exhibiting a nearly ideal architecture for the patterned perpendicular recording medium. The evolution of such compositional separation and topological nanoscale ordering is reasonably understood based on a three dimensional (3D) phase-field microelasticity (PFM) model.Ph.D.Includes bibliographical references.by Chenglin Zhan
On the General Chain Pair Simplification Problem
No full textThe Chain Pair Simplification problem (CPS) was posed by Bereg et al. who were motivated by the problem of efficiently computing and visualizing the structural resemblance between a pair of protein backbones. In this problem, given two polygonal chains of lengths n and m, the goal is to simplify both of them simultaneously, so that the lengths of the resulting simplifications as well as the discrete Frechet distance between them are bounded. When the vertices of the simplifications are arbitrary (i.e., not necessarily from the original chains), the problem is called General CPS (GCPS).
In this paper we consider for the first time the complexity of GCPS under both the discrete Frechet distance (GCPS-3F) and the Hausdorff distance (GCPS-2H). (In the former version, the quality of the two simplifications is measured by the discrete Fr'echet distance, and in the latter version it is measured by the Hausdorff distance.) We prove that GCPS-3F is polynomially solvable, by presenting an widetilde-O((n+m)^6 min{n,m}) time algorithm for the corresponding minimization problem. We also present an O((n+m)^4) 2-approximation algorithm for the problem. On the other hand, we show that GCPS-2H is NP-complete, and present an approximation algorithm for the problem
Genomic Scaffold Filling Revisited
No full textThe genomic scaffold filling problem has attracted a lot of attention recently. The problem is on filling an incomplete sequence (scaffold) I into I', with respect to a complete reference genome G, such that the number of adjacencies between G and I' is maximized. The problem is NP-complete and APX-hard, and admits a 1.2-approximation. However, the sequence input I is not quite practical and does not fit most of the real datasets (where a scaffold is more often given as a list of contigs). In this paper, we revisit the genomic scaffold filling problem by considering this important case when, (1) a scaffold S is given, the missing genes X = c(G) - c(S) can only be inserted in between the contigs, and the objective is to maximize the number of adjacencies between G and the filled S' and (2) a scaffold S is given, a subset of the missing genes X' subset X = c(G) - c(S) can only be inserted in between the contigs, and the objective is still to maximize the number of adjacencies between G and the filled S''. For problem (1), we present a simple NP-completeness proof, we then present a factor-2 greedy approximation algorithm, and finally we show that the problem is FPT when each gene appears at most d times in G. For problem (2), we prove that the problem is W[1]-hard and then we present a factor-2 FPT-approximation for the case when each gene appears at most d times in G
Fréchet Distance for Uncertain Curves
No full textIn this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves.
We prove that both problems are NP-hard for the continuous Fréchet distance, and the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound discrete Fréchet distance can be computed in polynomial time using dynamic programming. Furthermore, we show that computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments.
On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly δ-separated. Finally, we study the setting with Sakoe - Chiba bands, restricting the alignment of the two curves, and give polynomial-time algorithms for upper bound and expected (discrete) Fréchet distance for point-set-modelled uncertainty regions
Metric Violation and Similarity
No full textMetric data plays an important role in various settings, for example, in metric-based indexing,
clustering, classification, and approximation algorithms in general. Often such tasks require
the data to be metric, though for various reasons this basic property may not be satisfied.
The first topic we consider is the metric violation distance problem, which seeks to minimally
modify the data to make it metric, and thereby finding the nearest metric data set. Three
variants are considered, one admitting a polynomial time algorithm. The other variants are
shown to be APX-hard, and an approximation is given. We also introduce and give results
for the generalized metric violation distance problem, where there are no longer constraints
on all pairs.
The second topic concerns the fundamental computational task of assessing the similarity of
ordered data sets, i.e. the similarity of two trajectories. Here we introduce the Fréchet gap
distance, which in some ways better captures the intuitive notions of curve similarity when
comparing to the previous Standard Fréchet distance. In addition, a polynomial time exact
algorithm and a much faster 1 + approximation to compute this measure will be given.NSF CRII Award 1566137 and CAREER Award 175078
The Measurement of Integrated Human Service Network (The Children's Treatment Network of Simcoe York)
No full textTitle: The Measurement of Integrated Human Service Network (The Children's Treatment Network of Simcoe York), Author: Chenglin Ye, Location: ThodeCommunity-based human services have traditionally been provided by autonomous
service agencies. They have their own funding source and independent process.
Integration has been advocated as a key strategy to integrate different agencies together
to provide multiple services for a targeted community. The Children's Treatment Network
(CTN) of Simcoe York is a network of agencies and organizations providing services to
children with multiple needs and their families in Simcoe County and York Region. This
study was designed to evaluate the different levels of integrated service approaches for
children on outcomes. The study consisted of two parts: phase I and phase II
measurement. Our project covered phase I measurement with the following objectives. Clinically,
we aimed to evaluate agencies' integration in the network, promote discussion, and
determine any interrelationship between a network's integration and its functioning. The
statistical objectives were to quantify the network integration for agency, to represent the
overall integration, to quantify the association between network's integration and
functioning and to assess the sensitivity of results. We measured agencies' integration through measuring its agreement in
collaboration with other agencies in the network. The higher agreement in collaboration
indicates a better services integration. We defined four different agreement measures
from different perspectives. The agreement based on group's perception was defined to
be the primary measure. We used mean difference, percentage and the Kappa statistic
to measure the agreement for each agency. Correlation and regression analyses were
applied in investigating the association between network's integration and its functioning. The sensitivity of the results was analyzed by examining the re-sampling bias of
bootstrapping regression models. Agreement measures were consistent for each agency. In Simcoe, agencies had
an average agreement 0.874 (S.D. 0.213) in mean difference, 46.63 (S.D. 12.91) in
percentage and 0.258 (S.D. 0.143) in Kappa. Agencies of York had average agreements
of 0.662 (S.D. 0.204), 49.36 (S.D. 13.06) and 0.282 (S.D. 0.121), respectively. Agency
10 and 33 in Simcoe and Agency 14 in York were found to have the highest agreement.
Agency 3 and 21 in Simcoe and Agency 8 and 9 in York, on the other hand, were found
to have the lowest agreement. Different graphical displays illustrated that the overall
agreement in collaboration was low and the agencies in York generally had a higher
agreement. Correlation analysis showed that synergy and agencies' perception of pros
and cons were significantly correlated with the primary percentage agreement. In
regression analysis, we did not find any significant functioning component. However,
synergy was found to be much more associated with agreement than the other
components. The estimates were 11.48% (-1.03%, 24.00%) and 11.21% (-2.48%,
24.90%) in un-weighted and weighted models respectively. Bootstrapping regression
analysis showed that the results were robust to a change of sample. We concluded that the level of integration of CTN was low because the agencies
generally had poor agreement in collaboration. Synergy was the most important
component associated with the network's integration. Other functioning components
detected were also associated with the integrating process but were less clinically
important. We discussed the statistical approaches used in other contexts and some of
their strength and weaknesses. We also considered some key limitations of the study.
This study was a baseline measurement of CTN of Simcoe York for further analysis. The
results provided a basis for future enhancement of integration of the network. Our
experiences also provided ideas for improving design and analysis in integrated network
measurement.ThesisMaster of Science (MS
RETRACTED ARTICLE: Stem-like cells of various origins showed therapeutic effect to improve the recovery of spinal cord injury
No full textStem-like cells of various origins showed therapeutic effect to improve the recovery of spinal cord injuryWe, the Editors and Publisher of the journal Artificial Cells, Nanomedicine, and Biotechnology, have retracted the following article:Jian Kang, Chenglin Zhang, Zhongzheng Zhi, Yingjie Wang, Jingdong Liu, Furong Wu & Guanghui Xu (2020) Stem-like cells of various origins showed therapeutic effect to improve the recovery of spinal cord injury, Artificial Cells, Nanomedicine, and Biotechnology, 48:1, 627–638, DOI: 10.1080/21691401.2020.1725031Following publication of this article, concerns about the scientific integrity of the article were brought to the Publisher and Editor’s attention.Whilst the authors were fully cooperative with the investigation and able to answer some questions, they were unable to provide the original western blot data.In addition, concerns remain about the methods used for the animal experiments. As these concerns directly impact the reported results and conclusions, the Editor and Publisher have agreed to retract the article to ensure correction of the scholarly record. The corresponding author has been informed. The authors do not agree with the retraction.We have been informed in our decision-making by our policy on publishing ethics and integrity and the COPE guidelines on retractions. The retracted article will remain online to maintain the scholarly record, but it will be digitally watermarked on each page as ‘Retracted’
- …
