O(n) construction of Suffix trees using Ukkonon’s algorithm.O(n) LCA preprocess on Suffix Arrays to solve a variety of string problems.O(n) method of suffix array construction.O(n * logn) method of suffix array construction.O(n * logn^2) method of suffix array construction.O(n^2 * logn) Naive method of suffix array construction.Suggested Reading - Cormen chapter on Strings.KnuthMorrisPratt algorithm (Problems - NHAY, PERIOD on SPOJ).Suggested Reading - Computational Geometry: Algorithms and applications.CultureGrowth, PolygonCover on Topcoder.RAIN2, SEGMENTS, ARCHPLG, BALLOON, CIRCLES, COMPASS, EOWAMRT, ICERINK on SPOJ. BSHEEP, BULK, SEGVIS, CONDUIT, RUNAWAY, DIRVS, RAIN1, SHAMAN, TCUTTER, LITEPIPE, RHOMBS, FSHEEP,įLBRKLIN, CERC07P, BAC, ALTARS, CERC07C, NECKLACE, CH3D, RECTANGL, POLYSSQ, FOREST2, KPPOLY,.O(logn) algorithm with O(n * logn) preprocessing for convex polygons.Voronoi Diagrams of n points in O(n * logn) using Fortune’s algorithm.Delaunay Triangulation of n points in O(n * logn).Problems - Follow the tutorial for list of problems.Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.
Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn).Online construction of 3-D convex hull in O(n^2).Graham Scan algorithm for Convex Hull O(n * log(n)).Competitive Programming Syllabus Geometry
0 kommentar(er)
