# UNDF: UNDF-2026-000000483
# open3d-0002: RandomSampler::operator() — O(S²) std::find on samples vector inside rejection-sampling loop

## Location
`cpp/open3d/geometry/PointCloudSegmentation.cpp` lines 31–46
Repository: https://github.com/isl-org/Open3D

## Severity
**MEDIUM** — Called `num_iterations` times (typically 100–1000) during RANSAC plane segmentation. Each call uses rejection sampling with std::find on the growing `samples` vector. For a sample_size S, each call is O(S²) expected. The developer comment acknowledges "Well, this is slow." Total: O(num_iterations × S²). For ransac_n=3 (default), S=3 and impact is small, but for custom higher ransac_n values the overhead is measurable.

## Complexity
- Before: O(S²) per sample call — std::find on growing `samples` vector inside while loop
- After: O(S) per sample call — unordered_set for O(1) duplicate detection

## Defective Code

```cpp
// PointCloudSegmentation.cpp:31-46
std::vector<T> operator()(size_t sample_size) {
    std::vector<T> samples;
    samples.reserve(sample_size);

    size_t valid_sample = 0;
    while (valid_sample < sample_size) {
        const size_t idx = utility::random::RandUint32() % total_size_;
        // Well, this is slow. But typically the sample_size is small.
        if (std::find(samples.begin(), samples.end(), idx) ==
            samples.end()) {
            samples.push_back(idx);
            valid_sample++;
        }
    }
    return samples;
}
```

**Problem:** `std::find` on `samples` is O(valid_sample) inside the while loop. As
`valid_sample` grows from 0 to `sample_size`, the total work is 0+1+2+...+(S-1) = O(S²).
Called `num_iterations` times, total is O(num_iterations × S²).

## Fixed Code

```cpp
std::vector<T> operator()(size_t sample_size) {
    std::vector<T> samples;
    samples.reserve(sample_size);
    std::unordered_set<T> seen;
    seen.reserve(sample_size);

    while (samples.size() < sample_size) {
        const size_t idx = utility::random::RandUint32() % total_size_;
        if (seen.insert(idx).second) {  // O(1) duplicate detection
            samples.push_back(idx);
        }
    }
    return samples;
}
```

## CWE
CWE-407: Inefficient Algorithmic Complexity — O(S²) → O(S) per sample call
