By Demaine E., et al.
Read Online or Download The open problems project PDF
Similar computers books
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.
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.
Specified factor: chosen papers from PMAPS 2002 -Conference on Probabilistic tools utilized to energy structures, Naples 2002
- Computer Science Approach to Quantum Control
- Ubiquitous Computing and Multimedia Applications: International Conference, UCMA 2010, Miyazaki, Japan, June 23-25, 2010. Proceedings (Communications in Computer and Information Science)
- Bayesian Approach to Image Interpretation
- Emphasizing Distributed Systems
- Research and Education in Robotics -- EUROBOT 2008: International Conference, Heidelberg, Germany, May 22-24, 2008. Revised Selected Papers (Communications in Computer and Information Science, 33)
Additional info for The open problems project
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.