Related Experiment Video
Updated: May 13, 2026
11:06
3D Printing of Preclinical X-ray Computed Tomographic Data Sets
Published on: March 22, 2013
Blocking Delaunay triangulations
Oswin Aichholzer1, Ruy Fabila-Monroy, Thomas Hackl
1Institute for Software Technology, University of Technology, Graz, Austria.
Computational Geometry : Theory and Applications
|March 14, 2013
Summary
Researchers determined the number of white points needed to block black points in Delaunay triangulations. Approximately n/2 white points suffice, with fewer needed for points in convex position, and at least n/4 are necessary.
Area of Science:
- Computational Geometry
- Combinatorial Geometry
- Geometric Graph Theory
Background:
- The problem involves understanding the structure of Delaunay triangulations.
- The concept of 'blocking' a set of points is introduced using Delaunay triangulation properties.
- General position and convex position are key configurations for the point sets.
Purpose of the Study:
- To establish bounds on the minimum number of white points required to block a set of black points in a Delaunay triangulation.
- To analyze how the configuration of black points (general vs. convex position) affects the blocking set size.
- To determine necessary and sufficient conditions for blocking a set of points.
Main Methods:
- Analysis of Delaunay triangulations of point sets in the plane.
- Combinatorial arguments to derive upper and lower bounds for the size of the blocking set.
- Consideration of specific point set configurations, including general and convex positions.
Main Results:
- Proved that approximately n/2 white points are always sufficient to block a set of n black points.
- Showed that for black points in convex position, approximately n/3 white points are sufficient.
- Established a lower bound, proving that at least n/4 white points are always necessary to block the set.
Conclusions:
- The study provides tight bounds for the size of the smallest blocking set in Delaunay triangulations.
- The results offer insights into the interplay between point set configurations and triangulation properties.
- This work contributes to the understanding of geometric covering and blocking problems.
Related Concept Videos
01:20Mesh Analysis
Mesh analysis is a valuable method for simplifying circuit analysis using mesh currents as key circuit variables. Unlike nodal analysis, which focuses on determining unknown voltages, mesh analysis applies Kirchhoff's voltage law (KVL) to find unknown currents within a circuit. This method is particularly convenient in reducing the number of simultaneous equations that need to be solved.
A fundamental concept in mesh analysis is the definition of meshes and mesh currents. A mesh is a closed...
A fundamental concept in mesh analysis is the definition of meshes and mesh currents. A mesh is a closed...
01:21Boundary Conditions: Lossless Lines
Consider a single-phase, two-wire, lossless transmission line terminated by an impedance at the receiving end and a source with Thevenin voltage and impedance at the sending end. The line, with length, has a surge impedance and wave velocity determined by the line's inductance and capacitance.
At the receiving end, the boundary condition states that the voltage equals the product of the receiving-end impedance and current. This relationship is expressed as a function of the incident and...
At the receiving end, the boundary condition states that the voltage equals the product of the receiving-end impedance and current. This relationship is expressed as a function of the incident and...
01:21Plastic Deformations of Members with a Single Plane of Symmetry
When a structural member undergoes plastic deformation due to bending, it is crucial to understand the position of the neutral axis and the stress distribution. This member, characterized by a single plane of symmetry, exhibits a uniform stress distribution, with negative stress above the neutral axis and positive stress below. Notably, the neutral axis does not align with the centroid of the cross-section. This misalignment is typical in cases where the cross-section is not rectangular or...
01:27Gauss's Law: Planar Symmetry
A planar symmetry of charge density is obtained when charges are uniformly spread over a large flat surface. In planar symmetry, all points in a plane parallel to the plane of charge are identical with respect to the charges. Suppose the plane of the charge distribution is the xy-plane, and the electric field at a space point P with coordinates (x, y, z) is to be determined. Since the charge density is the same at all (x, y) - coordinates in the z = 0 plane, by symmetry, the electric field at P...
02:57Coordination Number and Geometry
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.
01:06Parallel-axis Theorem
The parallel-axis theorem provides a convenient and quick method of finding the moment of inertia of an object about an axis parallel to the axis passing through its center of mass. Consider a thin rod as an example. There is a striking similarity between the process of finding the moment of inertia of a thin rod about an axis through its middle, where the center of mass lies, and about an axis through its end using the conventional method. In the conventional method, the concept of linear mass...