Optimally fast incremental Manhattan plane embedding and planar tight span construction

zbMATH Open1404.68189MaRDI QIDQ2968080FDOQ2968080

Authors: David Eppstein 

Publication date: 9 March 2017

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

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)

Cited In (9)

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

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)