Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Coordination Number and Geometry02:57

Coordination Number and Geometry

15.9K
For transition metal complexes, the coordination number determines the geometry around the central metal ion. Table 1 compares coordination numbers to molecular geometry. The most common structures of the complexes in coordination compounds are octahedral, tetrahedral, and square planar.
15.9K
Wilcoxon Signed-Ranks Test for Matched Pairs01:09

Wilcoxon Signed-Ranks Test for Matched Pairs

144
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...
144
Collisions in Multiple Dimensions: Problem Solving01:06

Collisions in Multiple Dimensions: Problem Solving

4.2K
In multiple dimensions, the conservation of momentum applies in each direction independently. Hence, to solve collisions in multiple dimensions, we should write down the momentum conservation in each direction separately. To help understand collisions in multiple dimensions, consider an example.
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
4.2K
Sign Test for Matched Pairs01:17

Sign Test for Matched Pairs

143
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...
143
Equivalent Couples01:28

Equivalent Couples

294
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...
294
Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

12.2K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.2K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Assessing optic nerve integrity in optic neuritis with conventional magnetic resonance imaging.

AJNR. American journal of neuroradiology·2026
Same author

Optic nerve imaging with OCT predicts disease progression and monitors brain and spinal atrophy in primary progressive multiple sclerosis.

Multiple sclerosis (Houndmills, Basingstoke, England)·2026
Same author

Connectivity with Uncertainty Regions Given as Line Segments.

Algorithmica·2024
Same author

Trans-Synaptic Degeneration in the Visual Pathway in Patients With Myelin Oligodendrocyte Glycoprotein Antibody-Associated Disease.

Neurology·2024
Same author

The OSCAR-MP Consensus Criteria for Quality Assessment of Retinal Optical Coherence Tomography Angiography.

Neurology(R) neuroimmunology & neuroinflammation·2023
Same author

Guest Editors' Foreword.

Discrete & computational geometry·2022
Same journal

Some Fast Algorithms for Curves in Surfaces.

Discrete & computational geometry·2026
Same journal

A Full Halin Grid Theorem.

Discrete & computational geometry·2026
Same journal

Stability and Inference of the Euler Characteristic Transform.

Discrete & computational geometry·2026
Same journal

Error Resilient Space Partitioning.

Discrete & computational geometry·2026
Same journal

A Faithful Discretization of Verbose Directional Transforms.

Discrete & computational geometry·2026
Same journal

Maximum Betti Numbers of Čech Complexes.

Discrete & computational geometry·2026
See all related articles

Related Experiment Video

Updated: Jul 14, 2025

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.3K

Maximum Matchings in Geometric Intersection Graphs.

Édouard Bonnet1, Sergio Cabello2,3, Wolfgang Mulzer4

  • 1Université de Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, Lyon, France.

Discrete & Computational Geometry
|October 9, 2023
PubMed
Summary
This summary is machine-generated.

This study presents an efficient algorithm for finding maximum matchings in geometric intersection graphs. The new method achieves high probability time complexity, improving computational efficiency for complex geometric problems.

Keywords:
Computational geometryDisk graphGeometric intersection graphMatchingUnit-disk graph

More Related Videos

Estimation of Contact Regions Between Hands and Objects During Human Multi-Digit Grasping
09:41

Estimation of Contact Regions Between Hands and Objects During Human Multi-Digit Grasping

Published on: April 21, 2023

1.6K
The HoneyComb Paradigm for Research on Collective Human Behavior
06:48

The HoneyComb Paradigm for Research on Collective Human Behavior

Published on: January 19, 2019

9.4K

Related Experiment Videos

Last Updated: Jul 14, 2025

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.3K
Estimation of Contact Regions Between Hands and Objects During Human Multi-Digit Grasping
09:41

Estimation of Contact Regions Between Hands and Objects During Human Multi-Digit Grasping

Published on: April 21, 2023

1.6K
The HoneyComb Paradigm for Research on Collective Human Behavior
06:48

The HoneyComb Paradigm for Research on Collective Human Behavior

Published on: January 19, 2019

9.4K

Area of Science:

  • Computational Geometry
  • Graph Theory
  • Algorithm Analysis

Background:

  • Maximum matching is a fundamental problem in graph theory with applications in various fields.
  • Geometric intersection graphs, representing relationships between geometric objects, pose unique computational challenges.
  • Existing algorithms for maximum matching in general graphs are often too slow for large geometric datasets.

Purpose of the Study:

  • To develop a computationally efficient algorithm for finding maximum matchings in geometric intersection graphs.
  • To reduce the complexity of the maximum matching problem in general geometric intersection graphs to cases with bounded density.
  • To analyze the time complexity of the proposed algorithm, considering matrix multiplication and graph density.

Main Methods:

  • Combining algebraic methods, specifically matrix rank computation via Gaussian elimination.
  • Leveraging the property of small separators in geometric intersection graphs.
  • Reducing general geometric intersection graph problems to bounded density cases.

Main Results:

  • A maximum matching in a geometric intersection graph G with n objects can be found in O(n log n) time with high probability.
  • The algorithm is applicable to subgraphs of G, provided a geometric representation is available.
  • Efficient solutions are demonstrated for translates of convex objects and planar disks with bounded radii.

Conclusions:

  • The proposed algorithm offers a significant improvement in finding maximum matchings for geometric intersection graphs.
  • The integration of algebraic techniques and geometric properties provides a powerful approach to complex graph problems.
  • The findings have implications for various applications involving spatial data and network analysis.