Fast geometric approximation techniques and geometric embedding problems

DOI10.1016/0304-3975(92)90252-BMaRDI QIDQ1202926zbMATH OpenFDO

Authors Howard Karloff, Prabhakar Raghavan, Baruch Schieber, M. W. Bern

Publication date 22 April 1993

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

Full work available at URL https://doi.org/10.1016/0304-3975(92)90252-B

zbMATH Keywords

approximationfast approximation algorithmsgeometric embedding problemsminimum spanning treeplanesortingstartree

Mathematics Subject Classification ID

Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Review text

A new notion of approximate geometric sorting is used to devise an algorithm that gives a \((1+\varepsilon)\)-approximation to the 1- dimensional minimum spanning tree (MSP) (or traveling sales man path (TSP)) of \(n\) colinear points in time \(O(n+n\log(1/\varepsilon)/\log n)\). The same notion is used to devise two schemes that approximate the Euclidean minimum spanning tree (EMST) to within a factor of \(1+\varepsilon\). A consequence of this EMST approximations is a \((2+\varepsilon)\)- approximation scheme for the Euclidean TSP, running in time \(O(n\log\log n)\) for any fixed \(\varepsilon\). In the final section, the approximate sorting and MST algorithms are used to get fast approximation algorithms for three geometric embedding problems---for a star in the plane, a complete binary tree onto points on the line and a tree of fixed maximum degree onto the points on the plane.

Recommendations

• A fast and simple algorithm for computing approximate Euclidean minimum spanning trees
• Faster geometric \(k\)-point MST approximation
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Minimum Spanning Trees in k-Dimensional Space
• scientific article; zbMATH DE number 1775442

Cites work

• Approximate minimum weight matching on points in k-dimensional space
• Approximation algorithms for convex hulls
• Design and implementation of an efficient priority queue
• Fibonacci heaps and their uses in improved network optimization algorithms
• Graphs whose every transitive orientation contains almost every relation
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4064519 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Minimum Spanning Trees in k-Dimensional Space
• On optimal linear arrangements of trees
• Sorting helps for Voronoi diagrams
• The complexity of restricted spanning tree problems
• Upper bounds for sorting integers on random access machines
• Wafer-Scale Integration of Systolic Arrays

Cited in

(5)

• Two results on linear embeddings of complete binary trees
• Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
• Combinatorial theorems about embedding trees on the real line
• A linear-time approximation algorithm for the minimum-length geometric embedding of trees
• Well-separated pair decomposition in linear time?

This page was built for publication: Fast geometric approximation techniques and geometric embedding problems

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