Introduction

This problem is easy or interesting depending on what “any visible vertex” means. In a simple polygon, every vertex is automatically visible from its two neighbors, so if adjacent vertices count, the answer is constant time rather than linear time.

The Trivial Case: Adjacent Vertices Are Visible

Let the polygon vertices be stored in boundary order as v[0] ... v[n-1]. For a given vertex v[i], the vertices v[i-1] and v[i+1] are connected to it by polygon edges. In a simple polygon, those edges lie on the boundary, so those two vertices are visible from v[i].

That means the literal problem has a very small solution:

1def any_visible_neighbor(vertices, i):
2    n = len(vertices)
3    prev_index = (i - 1) % n
4    next_index = (i + 1) % n
5    return prev_index, next_index
6
7polygon = [(0, 0), (4, 0), (5, 2), (3, 4), (0, 3)]
8print(any_visible_neighbor(polygon, 2))

This runs in O(1) time and does not need geometric testing.

When a Linear-Time Algorithm Becomes Meaningful

Usually the interesting version is: find a visible non-adjacent vertex, or determine one by geometric inspection without relying on the trivial boundary neighbors.

For a simple polygon, a standard way to reason about visibility from a vertex is to look for a valid diagonal. A diagonal between v[i] and v[j] is visible if the segment stays inside the polygon except at its endpoints. Testing one candidate diagonal by brute force requires checking for intersections with polygon edges, which is O(n).

If you only need one visible non-adjacent vertex, scanning candidates and stopping at the first valid one gives a simple implementation, though in the worst case it becomes quadratic. Linear-time algorithms exist in more specialized treatments using polygon structure, but most practical codebases choose the simpler intersection-based method because it is easier to implement and verify.

A Practical Visibility Test

The following Python example checks whether a segment from one vertex to another intersects any non-incident polygon edge. It is not the asymptotically optimal algorithm, but it is a correct and runnable baseline.

1from math import isclose
2
3
4def orient(a, b, c):
5    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
6
7
8def on_segment(a, b, p):
9    return (min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and
10            min(a[1], b[1]) <= p[1] <= max(a[1], b[1]) and
11            isclose(orient(a, b, p), 0.0, abs_tol=1e-9))
12
13
14def segments_intersect(a, b, c, d):
15    o1 = orient(a, b, c)
16    o2 = orient(a, b, d)
17    o3 = orient(c, d, a)
18    o4 = orient(c, d, b)
19
20    if o1 == 0 and on_segment(a, b, c):
21        return True
22    if o2 == 0 and on_segment(a, b, d):
23        return True
24    if o3 == 0 and on_segment(c, d, a):
25        return True
26    if o4 == 0 and on_segment(c, d, b):
27        return True
28
29    return (o1 > 0) != (o2 > 0) and (o3 > 0) != (o4 > 0)
30
31
32def visible(vertices, i, j):
33    n = len(vertices)
34    a, b = vertices[i], vertices[j]
35
36    for k in range(n):
37        c = vertices[k]
38        d = vertices[(k + 1) % n]
39        if k in (i, j) or (k + 1) % n in (i, j):
40            continue
41        if segments_intersect(a, b, c, d):
42            return False
43    return True
44
45
46def first_non_adjacent_visible(vertices, i):
47    n = len(vertices)
48    for j in range(n):
49        if j in ((i - 1) % n, i, (i + 1) % n):
50            continue
51        if visible(vertices, i, j):
52            return j
53    return None

This implementation is useful for experimentation and for validating more advanced algorithms.

Interpreting the Theoretical Result

If your source insists on linear time, it is usually talking about a stronger geometry result, not the trivial “pick a neighbor” answer. For example, some algorithms exploit polygon monotonicity, triangulation, or a structured scan of candidate diagonals.

Those methods are worth studying in an algorithms course, but they are far more complex than most applications need. In production code, the right answer is often:

• use the O(1) neighbor solution if adjacent vertices count
• use a simple visibility test if the polygon sizes are moderate
• use a more advanced visibility structure only if performance profiling shows the need

Common Pitfalls

The biggest mistake is missing the trivial case. If the problem statement says “any visible vertex,” adjacent vertices already solve it.

Another mistake is assuming that a segment with no edge intersections is always a valid internal diagonal. Degenerate cases around boundary contact and non-simple polygons need careful handling.

A third issue is discussing linear-time visibility algorithms without stating the polygon model. Results for simple polygons, monotone polygons, and polygons with holes are not interchangeable.

Summary

• In a simple polygon, each vertex can always see its two adjacent vertices.
• If adjacent vertices count, the problem is O(1), not O(n).
• The interesting version is usually “find a non-adjacent visible vertex.”
• A practical implementation checks candidate segments against polygon edges.
• Linear-time results usually rely on stronger assumptions or more advanced geometry machinery.