完美的匹配与交叉的完美匹配
Oswin Aichholzer1, Ruy Fabila-Monroy2, Philipp Kindermann3
1Institute of Software Technology, Graz University of Technology, Inffeldgasse 16b, 8010 Graz, Austria.
Algorithmica
|March 14, 2024
概括
这项研究探讨了几何点集中的完美匹配,证明对于大n,与任意数量的交叉点k存在完美匹配. 凸点集最小化和最大化特定k值的交叉计数.
科学领域:
- 计算几何学的计算几何学
- 组合学是一种组合学.
- 图形理论 图形理论
背景情况:
- 完美的匹配是图中非相邻的顶点的对.
- 平面完美匹配是没有边缘交叉的完美匹配的图纸.
- 加泰罗尼亚数字量化了形位置的n点的平面完美匹配的数量.
研究的目的:
- 将完美匹配的理解推广到平面配置之外.
- 为了研究具有特定数量的边缘交叉点 (k) 的完美匹配的数量.
- 确定点集配置如何影响在完美匹配中交叉数的分布.
主要方法:
- 在一般位置的n个点的集合上对完美匹配的直线图的分析.
- 组合论证以确定十字路口数量的存在和限制.
- 对点集的交叉数分布的比较,一般而不是形位置.
主要成果:
- 对于足够大的n,一般位置上的任何一组点都允许与任何k的正确k个交叉点完全匹配.
- 存在点集,所有完美的匹配最多有O{\displaystyle O} n^2的交叉点.
- 最多有 k 个交叉点的完美匹配的数量随着 n 的超指数增长,当 k 在 n 中是超线性的.
- 在凸起的位置上设置点,将最多有k交叉的完美匹配数量最小化,并最大化具有k交叉的匹配数量.
结论:
- 完全匹配的交叉点的数量高度依赖于点集的配置.
- 一般位置点集在实现特定交叉号码方面提供了更大的灵活性.
- 凸起的位置点集代表了最小化或最大化与某些交叉计数匹配的极端情况.
相关概念视频
01:17Sign Test for Matched Pairs
131
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...
To conduct the sign test, we first calculate the differences in...
131
01:34Crossing Over
146.8K
Unlike mitosis, meiosis aims for genetic diversity in its creation of haploid gametes. Dividing germ cells first begin this process in prophase I, where each chromosome—replicated in S phase—is now composed of two sister chromatids (identical copies) joined centrally.
The homologous pairs of sister chromosomes—one from the maternal and one from the paternal genome—then begin to align alongside each other lengthwise, matching corresponding DNA positions in a process...
The homologous pairs of sister chromosomes—one from the maternal and one from the paternal genome—then begin to align alongside each other lengthwise, matching corresponding DNA positions in a process...
146.8K
01:09Wilcoxon Signed-Ranks Test for Matched Pairs
123
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
123
01:28Equivalent Couples
287
In mechanical engineering, the concept of equivalent couples plays a crucial role in understanding and analyzing various mechanical systems.
Two couples are considered to be equivalent if they produce the same rotational effect on a rigid body. In other words, the two couples have the same magnitude and act in the same direction, causing the same angular displacement or acceleration in the body.
For instance, consider two couples lying in the plane of the page, with one having a pair of equal...
Two couples are considered to be equivalent if they produce the same rotational effect on a rigid body. In other words, the two couples have the same magnitude and act in the same direction, causing the same angular displacement or acceleration in the body.
For instance, consider two couples lying in the plane of the page, with one having a pair of equal...
287
02:27Trihybrid Crosses
23.3K
Trihybrid Crosses
Some of Mendel’s crosses examined three pairs of contrasting characteristics. Such a cross is called a trihybrid cross. A trihybrid cross is a combination of three individual monohybrid crosses. For example, plant height (tall vs. short), seed shape (round vs. wrinkled), and seed color (yellow vs. green).
The F1 generation plants of a trihybrid cross are heterozygous for all three traits and produce eight gametes. Upon self-fertilization, these gametes have an equal...
Some of Mendel’s crosses examined three pairs of contrasting characteristics. Such a cross is called a trihybrid cross. A trihybrid cross is a combination of three individual monohybrid crosses. For example, plant height (tall vs. short), seed shape (round vs. wrinkled), and seed color (yellow vs. green).
The F1 generation plants of a trihybrid cross are heterozygous for all three traits and produce eight gametes. Upon self-fertilization, these gametes have an equal...
23.3K
01:25Cross Product
244
The cross product is a fundamental concept in vector algebra that is a vector operation on two different vectors to obtain a third vector. Unlike the scalar product, the cross product results in a vector quantity perpendicular to both the original vectors.
The magnitude of the cross product is obtained by multiplying the magnitude of both the vectors and the sine of the angle between them. This means that a larger angle between the vectors will lead to a greater magnitude of the cross product.
The magnitude of the cross product is obtained by multiplying the magnitude of both the vectors and the sine of the angle between them. This means that a larger angle between the vectors will lead to a greater magnitude of the cross product.
244