The Farthest Color Voronoi Diagram in the Plane

Area of Science:

• Computational Geometry
• Geometric Algorithms
• Data Analysis

Background:

• The farthest-color Voronoi diagram (FCVD) is a geometric structure used in various computational problems.
• Existing research lacks detailed structural properties and refined complexity bounds for FCVD.
• Applications span facility location, shape matching, and handling data imprecision.

Purpose of the Study:

• To present novel structural properties of the farthest-color Voronoi diagram (FCVD).
• To refine combinatorial complexity bounds for the FCVD.
• To develop efficient algorithms for constructing the FCVD.

Main Methods:

• Analysis of the geometric and combinatorial properties of the FCVD.
• Development of algorithms based on divide-and-conquer or sweep-line approaches.
• Derivation of upper and lower bounds for the diagram's complexity.

Main Results:

• Established the FCVD complexity as O(n α(m) + str(P)), where str(P) represents straddles.
• Demonstrated a lower bound of Ω(n + m^2) for FCVD complexity.
• Presented an O((n + str(P)) log^3 n) construction algorithm, with O(n log n) for special cases.

Conclusions:

• The study provides a comprehensive understanding of FCVD structure and complexity.
• Efficient algorithms are now available for FCVD construction, improving practical applications.
• The refined bounds and algorithms contribute to advancements in computational geometry and related fields.