Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Approximate Algorithm
Computational Geometry
Convex Hull
Hamiltonian Cycle
Hamiltonian Path
Network Design
Spanning Tree
Hamiltonian Path Problem
Subscribe
Academic
Publications
Long Noncrossing Configurations in the Plane
Long Noncrossing Configurations in the Plane,10.1007/s0045401092779,Discrete & Computational Geometry,Adrian Dumitrescu,Csaba D. Tóth
Edit
Long Noncrossing Configurations in the Plane
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Adrian Dumitrescu
,
Csaba D. Tóth
We revisit some maximization problems for geometric networks design under the noncrossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1995). Given a set of n points in the plane in general position (no three points collinear), compute a longest noncrossing configuration composed of straight line segments that is: (a) a matching, (b) a Hamiltonian path, and (c) a spanning tree. We obtain some new results for (b) and (c), as well as for the
Hamiltonian cycle
problem. (i) For the longest noncrossing
Hamiltonian path
problem, we give an approximation algorithm with ratio . The previous best ratio, due to Alon et al., was . The ratio of our algorithm is close to on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. For instance “random” point sets meet the condition with high probability. The algorithm runs in O(n 7/3log n) time. (ii) For the longest noncrossing
spanning tree
problem, we give an approximation algorithm with ratio 0.502 which runs in O(nlog n) time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first rederive the result of Alon et al. with a faster algorithm and a very simple analysis. (iii) For the longest noncrossing
Hamiltonian cycle
problem, we give an approximation algorithm whose ratio is close to 2/π on a relatively broad class of instances: for point sets where the product 〈diameter×convex hull size〉 is much smaller than the maximum length matching. Again “random” point sets meet the condition with high probability. However, this algorithm does not come with a constant approximation guarantee for all instances. The algorithm runs in O(n 7/3log n) time. No previous approximation results were known for this problem.
Journal:
Discrete & Computational Geometry  DCG
, vol. 44, no. 4, pp. 727752, 2010
DOI:
10.1007/s0045401092779
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.springerlink.com
)
More »
References
(23)
RamseyType Results for Geometric Graphs, I
(
Citations: 17
)
G. Károlyi
,
J. Pach
,
G. Tóth
Journal:
Discrete & Computational Geometry  DCG
, vol. 18, no. 3, pp. 247255, 1997
Bipartite embeddings of trees in the plane
(
Citations: 22
)
M. Abellanas
,
J. García
,
G. Hernández
,
M. Noy
,
P. Ramos
EdgeRemoval and NonCrossing Configurations in Geometric Graphs
(
Citations: 3
)
Oswin Aichholzer
,
Sergio Cabello
,
Ruy FabilaMonroy
,
David FloresPe
,
Thomas Hackl
,
Clemens Huemer
,
Ferran HurtadoDavid
,
R. Wood
Conference:
European Workshop on Computational Geometry
, 2008
Long noncrossing configurations in the plane
(
Citations: 8
)
Noga Alon
,
Sridhar Rajagopalant
,
Subhash Suri
Conference:
Symposium on Computational Geometry  SOCG
, pp. 257263, 1993
APPROXIMATION ALGORITHMS FOR GEOMETRIC PROBLEMS
(
Citations: 83
)
Marshall Bern
,
David Eppstein
Published in 1995.
Sort by:
Citations
(1)
Bounds on the maximum multiplicity of some common geometric graphs
(
Citations: 1
)
Adrian Dumitrescu
,
André Schulz
,
Adam Sheffer
,
Csaba D. Tóth
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, vol. abs/1012.5, pp. 637648, 2011