Hi Thomas,
I get a "You do not have the required role." Can you make your proposal public, so that also non-mentors can view it? Well, on the other hand, I shouldn't spend too much time into this, so it's probably good that I can't see it.
It seems to me that I am not able to make it public, that's why I'll add it to this message. Personal Details - Name: Andrii Sydorchuk - College/University: Kyiv Taras Schevchenko National Universtiy - Course/Major: Cybernetics/Applied Mathematics - Degree Program (BS, MS, PhD, etc.): Master - Email: sydorchuk.andriy@gmail.com - Homepage: - - Availability: I plan to spend 6-8 hours per day (more if required). I've already started (reading articles), 20th of August. I don't think that any of this factors with affect my availability. Background Information Educational background: I've earned Bachelors Degree in Applied Mathematics (GPA 4.95). At the moment I am on the first course of my Master's program in Applied Mathematics. Courses taken: Algebra and Geometry, Mathematical Analysis, Discrete Mathematics, Programming, Differential Equations, Numeric Methods, Mathematical Logic and Algorithms Theory, Mathematica Modeling, etc. Programming background: 1) January 2010 - April 2010 - Google Company, Software Engineer Intern (Zurich, Switzerland). Responsible for managing workflow pipelines. 2) April 2009 - December 2009 - Scopicsoftware Company, C++ Algorithm Software Developer. Responsible for 2D/3D applications development. Programming interests: Algorithms, Data Structures, Computational Geometry; Software competitions: 2010 - Internal Google Code Jam 2010 - 7th place. 2009 - All Ukrainian Collegiate Programming Contest 2009 - 3d diploma. 2008 - Advanced to Google Code Jam 2008 semifinal (London). Languages, technologies and tools: C++, C#, Python, STL, MFC, Qt, OpenGL; 3D rendering; Interest in contribution to the Boost C++ libraries: become more familiar with Boost libraries; make contribution to the library used by lots of people; Interest in the project: I am interested in algorithms, data structures, analytical geometry. And all of them are included as part of Sweepline project. But the main idea is to become more familiar with Boost library (not only part I'll work on). Previous work in this area (Scopicsoftware): 1) Making improvement to the algorithm of finding center lines of standard fonts, however this project used wave algorithm approach. 2) Developing 3D CAD system for creating office cubicles. Implementation of Collada[1] 3D models importer. Adding support of YafaRay raytracing engine[2]. Development and improvement of algorithms for cubicles clustering and objects arrangement. Plans beyond Summer of Code: 1) continue implementation of computational geometry algorithms in Boost. 2) become more familiar with other parts of Boost library and work on them also. C++ (4.2) C++ Standard Library (4.3) Boost C++ Library (0.0, starting to learn) Subversion (2.0, only SVN) Software development environments: Visual Studio, emacs. Documentation tool: I haven't used any of them (will study one of them during April - May). Project Proposal Implement generic and robust sweepline algorithm for solving 2D Voronoi diagram and Delaunay triangulation problems. I will also implement Sweep Line algorithm visualization tool using OpenGL. This will slightly help during testing. Basically it will visualize all the execution process: site events, circle events, adding new sites to the beach line, removing sites and so on. During last month I'll implement benchmark tests. It is also a good idea to start with writing tests and add new cases during development. Basically implementation of sweepline requires next data structures: 1) Event queue (priority queue). We can split site events and circle events into two data structures[3]: a) site events may be stored in stl vector. Which will be sorted after reading input data. Complexity of sorting n*log(n), where n - is number of input sites. b) circle events may be stored in stl priority_queue. Adding new element, lookup, deletion will require log(n) time, where n is number of elements in the priority queue. 2) Sweepline (self-balanced binary tree). For sweepline it is good choice to use wrapper class (adapter pattern) of stl map or set. It is better to use map, because we can split keys and associated data (storing whatever our problem requires). For elements we can choose bisectores of two neihbour sites[4]. We will also need to define robust key comparer[5], as there might be precision problems. 3) Output data structures (half edges, double linked lists, etc.). I'll do further research in this area. Next degeneracies will require careful handling: 1) 2 or more events on a common vertical line; 2) event points coincide, e.g. 4 or more co-circular points; 3) a site coincides with event; Proposed Milestones and Schedule Present - end of May: design basic architecture, write test cases, read articles connected with the topic, learn Boost; start of June - mid of July: finish Voronoi and Delaunay triangulation implementation; mid of July - 20th of August: improve logic, make refactoring, work on performance, testing, finishing documentation, benchmark tests. *References* [1] - http://code.google.com/p/opencollada/ [2] - http://www.yafaray.org/ [3] - Kenny Wong, Hausi A. Muller. An Efficient Implementation of Fortune's Plane-Sweep Algorithm for Voronoi Diagrams. [4] - Mark de Berg. Computational Geometry: Algorithms and Applicatoins. Page.156. [5] - Ruud, B. Building a Mutable Set, 2003