Finding transversals for sets of simple geometric figures

DOI10.1016/0304-3975(85)90005-2zbMath0604.68080OpenAlexW2043127280MaRDI QIDQ1083215

Herbert Edelsbrunner

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90005-2

zbMATH Keywords

computer graphicsconvex hullcomputational geometryefficient algorithms for finding transversals

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)

Related Items

Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications ⋮ Largest and smallest convex hulls for imprecise points ⋮ Continuous location of dimensional structures. ⋮ Algorithms for high dimensional stabbing problems ⋮ The \(k\)-centrum straight-line location problem ⋮ Ordered stabbing of pairwise disjoint convex sets in linear time ⋮ Largest and smallest area triangles on imprecise points ⋮ Location of weighted anti-ordered median straight lines with Euclidean distances ⋮ Computing shortest transversals ⋮ Polyhedral line transversals in space ⋮ Efficient algorithm for transversal of disjoint convex polygons. ⋮ Transversal of disjoint convex polygons. ⋮ COMPUTING A SHORTEST WEAKLY EXTERNALLY VISIBLE LINE SEGMENT FOR A SIMPLE POLYGON

Cites Work

• Fast detection of polyhedral intersection
• Stabbing line segments
• An efficient algorithm for determining the convex hull of a finite planar set
• Linear Programming in Linear Time When the Dimension Is Fixed
• An on-line algorithm for fitting straight lines between data ranges
• Convex hulls of finite sets of points in two and three dimensions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item