Optimally fast incremental Manhattan plane embedding and planar tight span construction

MaRDI QIDQ2968080zbMATH OpenFDO

Authors David Eppstein

Publication date 9 March 2017

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• An algorithm for the construction of the tight span of finite subsets of the Manhattan plane
• Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
• Tight span of subsets of the plane with the maximum metric
• MANHATTONIAN PROXIMITY IN A SIMPLE POLYGON
• Embedding into the rectilinear grid

Cited in

(9)

• Bounds on the complexity of halfspace intersections when the bounded faces have small dimension
• Searching for realizations of finite metric spaces in tight spans
• Ramified rectilinear polygons: coordinatization by dendrons
• Linear-size planar Manhattan network for convex point sets
• An algorithm for the construction of the tight span of finite subsets of the Manhattan plane
• Tight span of path connected subsets of the Manhattan plane
• Tight span of subsets of the plane with the maximum metric
• Embedding into the rectilinear plane in optimal \(O(n^{2})\) time
• On the tight span of an antipodal graph

This page was built for publication: Optimally fast incremental Manhattan plane embedding and planar tight span construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2968080)