Related Experiment Video
Updated: Jan 1, 2026
08:34
Automated Charting of the Visual Space of Housefly Compound Eyes
Published on: March 31, 2022
2.2K
Dynamic Voronoi Diagram for Moving Disks
IEEE Transactions on Visualization and Computer Graphics
|December 17, 2019
Summary
We developed a new algorithm to create Voronoi diagrams for moving circular disks. This method efficiently tracks changes over time, aiding in collision avoidance for applications like autonomous vehicle traffic management.
Area of Science:
- Computational Geometry
- Spatial Analysis
Background:
- Voronoi diagrams are crucial for spatial analysis but are underexplored for dynamic systems.
- Applications in robotics and traffic management require understanding moving object interactions.
Purpose of the Study:
- To present a novel algorithm for constructing Voronoi diagrams of moving circular disks.
- To provide an efficient method for analyzing dynamic spatial relationships over a continuous time horizon.
Main Methods:
- Introduced a topology-oriented event-increment (TOI-E) algorithm.
- The algorithm computes the event history of the Voronoi diagram for moving disks.
- Achieves efficient computation with specific time and memory complexities.
Main Results:
- The TOI-E algorithm computes the event history in O(kF logn + kC n logn) time.
- Preprocessing requires O(n logn) time, with O(n + kF + kC) memory.
- Dynamic Voronoi diagrams can be constructed for any moment efficiently.
Conclusions:
- The proposed algorithm enables efficient dynamic Voronoi diagram construction for moving disks.
- This method is applicable to collision avoidance and traffic management for unmanned vehicles.
- Dynamic Voronoi diagrams offer a powerful platform for autonomous system navigation.
Related Concept Videos
01:17Design Example: Calculating Safe Diameter for Wind-Exposed Disc
322
Assessing safety in wind-exposed installations is crucial to preventing potential failures. This example explores the calculation and design adjustments needed to mount a circular disc on a building facade, where wind forces are a primary concern. A 4-meter diameter disc was initially designed as an aesthetic feature facing winds at a velocity of 25 meters per second, with an air density of 1.25 kilograms per cubic meter. Given these conditions, the drag force on the disc was determined using...
322
01:23Electric Field of a Charged Disk
3.0K
The simplest case of a surface charge distribution is the uniformly charged disk. Calculating its electric field also helps us calculate the electric field of a large plane of charge.
The system's symmetry is in the cylindrical directions across the plane of the charge. As a result, the electric fields created by various surface charge elements nullify each other in the direction parallel to the surface. Thereby, the resulting electric field is perpendicular to the plane. Since the disk is...
The system's symmetry is in the cylindrical directions across the plane of the charge. As a result, the electric fields created by various surface charge elements nullify each other in the direction parallel to the surface. Thereby, the resulting electric field is perpendicular to the plane. Since the disk is...
3.0K
01:18Fluid Movement Between Compartments
3.5K
The force applied by fluids against a surface, known as hydrostatic pressure, initiates the transfer of fluid among different compartments. Within our blood vessels, the blood's hydrostatic pressure is a result of the heart's pumping action. At the arteriolar end of capillaries, hydrostatic pressure (capillary blood pressure) exceeds the opposing colloid osmotic pressure created primarily by plasma proteins like albumin. This discrepancy in pressure propels plasma and nutrients from the...
3.5K
01:18pV-Diagrams
6.0K
The pV diagram, which is a graph of pressure versus volume of the gas under study, is helpful in describing certain aspects of the substance. When the substance behaves like an ideal gas, the ideal gas equation describes the relationship between its pressure and volume. On a pV diagram, it is common to plot an isotherm, which is a curve showing p as a function of V with the number of molecules and the temperature fixed. Then, for an ideal gas, the product of the pressure of the gas and its...
6.0K
01:34Velocity and Position by Graphical Method
9.4K
Velocity and position can be calculated from the known function of acceleration as a function of time. The total area under the acceleration-time graph and the velocity-time graph gives the change in velocity and position, respectively. In the case of an airplane, its acceleration is tracked using the inertial navigation system. The pilot provides the input of the airplane's initial position and velocity before takeoff. The inertial navigation system then uses the acceleration data to...
9.4K
01:11Relative Velocity in Two Dimensions
8.8K
Relative velocity is the velocity of an object as observed from a particular reference frame, or the velocity of one reference frame with respect to another reference frame. The concept of relative velocity can be used to describe motion in two dimensions. Consider a particle P and two reference frames S and S′. The position of the origin of S′ as measured in S is , the position of P as measured in S′ is , and the position of P as measured in S is , which can be evaluated by utilizing...
8.8K