Inselberg's hstar duality transforms containment testing into a visual pattern. A point is inside a convex set if and only if its polyline stays within the hstar envelope.
Standard point-in-convex-region tests use half-plane intersections, linear programming, or signed area. The parallel-coordinates equivalent is purely geometric.
The hstar is the family of curves in the parallel-coordinates plane corresponding to the boundary of a convex set. The containment test is immediate: an interior point's polyline lies entirely within the hstar envelope; an exterior point's crosses it.
Recall from explainer 03 that curves in Cartesian space produce families of line segments in parallel coordinates, and those families have envelopes. The hstar is the specific envelope that arises from the boundary of a convex set.
For a bounded convex region (a circle, say), every boundary point maps to a PC segment. The family sweeps out a region bounded by two envelope curves pinching at the endpoints — a generalized hyperbola, hence hstar (h*).
For a circle of radius centered at , the boundary is parameterized as . Each boundary point maps to a line segment in PC connecting on axis to on axis . As sweeps from 0 to , these segments trace the hstar.
The envelope of this family satisfies two conditions simultaneously: the family equation and the derivative with respect to the parameter vanish. For the circle, this produces the characteristic bowtie shape, widest at the height of the center and pinching to points at the extremes of the circle's vertical extent.
Here is Inselberg's result, stated precisely:
Theorem (Inselberg). Let S be a bounded convex set in and let h*(S) be its hstar representation in parallel coordinates. A point P lies inside S if and only if the line segment representing P in PC lies entirely within (or on the boundary of) the region enclosed by h*(S).
The test is visual and exact. The boundary maps to the envelope, the interior to the enclosed region, the exterior to everything outside.
Drag the test point in the Cartesian view, or drag the dots on the PC axes. When inside the circle, the polyline stays within the hstar. When outside, it crosses.
Figure 1. A circle in Cartesian space (left) and its hstar in parallel coordinates (right). The draggable test point's polyline is blue when contained and red when it exits the hstar envelope.
When the convex set is a polygon rather than a smooth curve, the hstar becomes piecewise linear. Each edge of the polygon is a line segment in Cartesian space. The family of points on that edge maps to a family of PC segments that sweep linearly, and their envelope is a pair of straight lines. The complete hstar is formed by joining these piecewise-linear envelope segments at the vertices.
The more vertices the polygon has, the more closely its hstar approximates the smooth bowtie of a circle. A triangle produces a hstar with sharp corners. A dodecagon is nearly smooth. In the limit, a polygon with infinitely many vertices is a circle, and the hstar converges to the smooth envelope.
Drag the test point. Adjust the vertex count to see the hstar refine from angular to smooth.
Figure 2. A regular convex polygon and its piecewise-linear hstar. More vertices produce a smoother envelope. The containment test still works: interior points produce contained polylines.
The name hstar comes from its connection to the classical hyperbola. For a circle, the envelope is symmetric. But an ellipse with eccentricity greater than zero produces an asymmetric bowtie where the envelope curves are segments of actual hyperbolas.
An ellipse with semi-axes and , rotated by angle , has the parameterization:
As eccentricity increases, the bowtie becomes more pronounced: wider on one side and narrower on the other. The rotation angle tilts the entire envelope. When , the ellipse is a circle and the hstar is symmetric. The hstar continuously deforms as you vary these parameters.
Figure 3. An ellipse in Cartesian space and its hstar envelope. Eccentricity controls how asymmetric the bowtie becomes. Rotation tilts the envelope. At zero eccentricity, this is the circle case from Figure 1.
Set operations swap across the duality:
The convex hull of the union of two convex sets corresponds to the intersection of their hstar regions in PC. The intersection of two convex sets corresponds to the union of hstar regions.
The reversal follows from projective duality. A point in the intersection satisfies both containment conditions, so its polyline lies inside both hstars. A point in the union satisfies at least one, so its polyline lies inside at least one hstar.
Figure 4. Two overlapping circles. Toggle between showing their intersection (Cartesian) mapped to the union of hstars (PC), and their union (Cartesian) mapped to the intersection of hstars (PC). The highlighted region in each view shows where the test is satisfied.
The containment test extends to higher dimensions. A convex set in 3D is represented in parallel coordinates with three axes. The set produces an hstar between axes 1-2 and another between axes 2-3. A point lies inside the convex set if and only if its polyline lies within both hstars simultaneously.
For a tetrahedron in 3D, each face is a triangle. The hstar between each adjacent pair of axes is the piecewise-linear envelope of the face projections.
Adjust the three sliders to move the test point through the tetrahedron. The polyline is blue when contained, red when it exits any hstar.
Figure 5. A tetrahedron in 3D represented across three parallel axes. The hstar envelopes between each axis pair are shown in gray. The test point's polyline must stay within both hstar regions to be inside the tetrahedron.
The hstar reveals more than containment. It reveals whether the set is convex in the first place. Inselberg showed that convex boundaries produce envelope curves that are smooth (no cusps), while non-convex boundaries produce envelopes with cusps or self-intersections.
This provides a visual convexity test: examine the hstar. If the envelope is cusp-free, the boundary is convex. If cusps appear, the set has concavities. The location of the cusp in PC tells you where the concavity occurs on the original boundary.
The purely geometric test. The containment test requires no linear programming, no half-plane intersection, no signed area computation. It reduces a potentially complex computational geometry problem to a visual pattern: does the polyline stay inside the envelope? This is remarkable because the algebraic test (solve a system of inequalities) and the geometric test (check visual containment) are exactly equivalent. Inselberg's duality makes the abstract concrete.
For higher dimensions, the test generalizes naturally. A convex set in produces an hstar between each pair of adjacent axes. A point is inside the set if and only if its polyline lies within every hstar simultaneously. The visual test scales: you check each inter-axis gap independently.