EFFICIENT ALGORITHMS FOR THE OPTIMAL-RATIO REGION DETECTION PROBLEMS IN DISCRETE GEOMETRY WITH APPLICATIONS

Area of Science:

• Computational geometry
• Medical image analysis
• Computer vision

Background:

• High-dimensional medical image segmentation presents challenges in accurately identifying regions.
• Existing methods may be biased by noise, leading to overly large or small region detection.
• Optimal-ratio region detection (ORD) is crucial for precise segmentation in complex datasets.

Purpose of the Study:

• To develop efficient algorithms for optimal-ratio region detection (ORD) in d-D (d ≥ 3) discrete spaces.
• To address challenges in high-dimensional medical image segmentation using novel computational techniques.
• To provide a unified algorithmic framework for solving ORD problems with normalized objective functions.

Main Methods:

• A unified algorithmic framework based on geometric structure characterization and graph transformation.
• Utilizing a hand probing technique to construct a convex hull for unknown 2-D points.
• Implementing probing oracles via minimum s-t cut computations in weighted directed graphs, with O(n) calls.

Main Results:

• Efficient polynomial-time algorithms for solving ORD problems in high dimensions.
• Demonstration that ORD problems can be solved by O(n) calls to a minimum s-t cut algorithm.
• For single heightfield surfaces, detection complexity reduces to a single maximum flow computation.

Conclusions:

• The developed framework offers efficient solutions for complex ORD problems in high-dimensional spaces.
• The approach provides a significant advancement for medical image segmentation tasks.
• This work lays the foundation for further research in high-dimensional geometric data analysis.