The open problems project by Demaine E., et al.

By Demaine E., et al.

Show description

Read Online or Download The open problems project PDF

Similar computers books

Fire in the Valley: The Birth and Death of the Personal Computer

Within the Nineteen Seventies, whereas their contemporaries have been protesting the pc as a device of dehumanization and oppression, a motley choice of collage dropouts, hippies, and electronics lovers have been engaged in anything even more subversive. enthusiastic about the assumption of having computing device strength into their very own arms, they introduced from their garages a hobbyist flow that grew into an undefined, and eventually a social and technological revolution.

STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006. Proceedings

This e-book constitutes the refereed complaints of the twenty third Annual Symposium on Theoretical facets of machine technological know-how, STACS 2006, held in Marseille, France, in February 2006. The fifty four revised complete papers offered including 3 invited papers have been rigorously reviewed and chosen from 283 submissions.

Compel (Vol. 23, 2004): Special Issue

Specified factor: chosen papers from PMAPS 2002 -Conference on Probabilistic tools utilized to energy structures, Naples 2002

Additional info for The open problems project

Sample text

59 References [BK98] Therese Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Comput. Geom. , 9:159–180, 1998. [DO03b] Erik D. Demaine and Joseph O’Rourke. Open problems from CCCG 2002. In Proceedings of the 15th Canadian Conference on Computational Geometry, August 2003. org/archive/cs/0212050. [ESW00] P. Eades, A. Symvonis, and S. Whitesides. Three dimensional orthogonal graph drawing algorithms. , 103:55–87, 2000. [LMS98] Yanpei Liu, Aurora Morgana, and Bruno Simeone. A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid.

In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, 2002. To appear. Problem 36: Inplace Convex Hull of a Simple Polygonal Chain Statement How much extra space is required to compute the convex hull of a simple polygonal chain or simple polygon in linear time? More precisely, given the n points in order along the chain in an array A, the alogorithm must re-arrange the points inplace in the array and output a number h so that the first h elements in the resulting array are the points on the convex hull in order.

In Proc. 10th Annu. ACM Sympos. Comput. , pages 383–384, 1994. [MO01] J. S. B. Mitchell and Joseph O’Rourke. Computational geometry column 42. Internat. J. Comput. Geom. , 11(5):573–582, 2001. Also in SIGACT News 32(3):63-72 (2001), Issue 120. 32 Problem 25: Polyhedral Surface Approximation Statement How efficiently can one compute a polyhedral surface that is an ǫ-approximation of a given triangulated surface in R3 ? ] Status/Conjectures Open. Partial and Related Results It is NP-hard to obtain the minimum-facet surface separating two nested convex polytopes [DG97], but polynomialtime approximation algorithms are known ([BG95, MS95, AS98]) for this case, and for separating two terrain surfaces, achieving factors within O(1) or O(log n) of optimal.

Download PDF sample

Rated 4.16 of 5 – based on 34 votes

Related posts