Patent Publication Number: US-9886527-B2

Title: Determining feasible splines with engineering constraints using projection methods

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit under 35 U.S.C. Section 119(e) of the following commonly-assigned U.S. provisional patent application(s), which is/are incorporated by reference herein: 
     U.S. Patent Application Ser. No. 61/753,338, entitled “PROJECTION METHODS FOR SOLVING FEASIBILITY AND BEST APPROXIMATION PROBLEMS WITH HALFSPACES”, filed on Jan. 16, 2013, by Heinz H. Bauschke and Valentin R. Koch. 
     This application is related to the following co-pending and commonly-assigned patent application, which application is incorporated by reference herein: 
     U.S. patent application Ser. No. 13/626,451, entitled “ROAD DESIGN OPTIMIZATION”, filed on Sep. 25, 2012, now U.S. Pat. No. 9,477,789, issued on Oct. 25, 2016, by Valentin R. Koch, which application claims priority to U.S. Provisional Application Ser. No. 61/539,793, entitled “ROAD DESIGN OPTIMIZATION”, filed on Sep. 27, 2011, by Valentin R. Koch. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates generally to road design, and in particular, to a method, apparatus, and article of manufacture for defining a vertical road profile design with engineering constraints. 
     2. Description of the Related Art 
     (Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.) 
     In road design, computer aided design (CAD) users try to draw road profiles that follow the existing ground as close as possible. This reduces the overall earthwork costs (cut and fill). However, in most cases, there are design constraints that need to be imposed on the profile, such as (1) maximum positive and negative grades, (2) minimal required grade for drainage (no flat sections allowed), (3) maximum grade change, and (4) the profiles need to go through some fixed points (intersections with other roads, etc.). 
     Often times, an initial design that follows the ground closely does not respect all of the constraints described above (e.g., infeasible with respect to one or more constraints). Prior art methods attempt to impose such constraints on an existing profile using linear programming (LP). An example of such a method is given in the publication “A note on: Spline technique for modeling roadway profile to minimize earthwork cost”, by Valentin Koch and Yves Lucet, Volume 6 (2), pages 393-400, Journal of Industrial and Management Optimization (Published March 2010). Some of the constraints (e.g., constraints 1, 3, and 4) can be incorporated as linear constraints into an LP. However, constraint (2) is not linear and can therefore not be added to an LP. A possible way to solve the problem with constraint (2) would be with the help of a mixed-integer linear program (MIP). There are several disadvantages for using a MIP. First, a MIP can be very slow and can take up to hours to solve large problem instances. Second, a MIP requires sophisticated solver software (often commercially licensed) to solve the problem. 
     In an LP approach, one uses linear equations and a complex algorithm such as the simplex algorithm or interior-point methods, to solve the problem. In a MIP approach, one adds integer variables to linear equations. In a MIP, the same algorithms as in an LP are used, but in a procedure called branch-and-bound, where an LP is solved thousands or millions of times. This makes the MIP approach very slow. 
     In view of the above, what is needed is a fast and accurate method for determining and modifying a spline to comply with a set of design constraints. In particular, it is desirable to use a method, apparatus, and system that can modify a civil engineering spline while satisfying a set of constraints that are both linear and non-linear. 
     SUMMARY OF THE INVENTION 
     Embodiments of the invention acquire an initial design/spline that follows the ground closely, but that does not respect all of the constraints (i.e., infeasible with respect to one or more constraints). The design is either altered such that it becomes feasible, or an indication is provided that there may be no profile that will satisfy all of the constraints. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Referring now to the drawings in which like reference numbers represent corresponding parts throughout: 
         FIG. 1  is an exemplary hardware and software environment used to implement one or more embodiments of the invention; 
         FIG. 2  schematically illustrates a typical distributed computer system using a network to connect client computers to server computers in accordance with one or more embodiments of the invention; 
         FIG. 3  illustrates the vertical profiles of a ground profile g, initial road design ƒ (t,v) , and final road design ƒ (t,w)  for a highway design near Kelowna, B.C., Canada in accordance with one or more embodiments of the invention; 
         FIG. 4  illustrates the logical flow for modifying a spline in accordance with one or more embodiments of the invention; 
         FIG. 5  illustrates an exemplary vertical road profile in accordance with one or more embodiments of the invention; 
         FIGS. 6A-6C  illustrate different slope bounds that may be utilized as constraints in accordance with one or more embodiments of the invention; and 
         FIG. 7  illustrates a slope constraint in accordance with one or more embodiments of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following description, reference is made to the accompanying drawings which form a part hereof, and which is shown, by way of illustration, several embodiments of the present invention. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention. 
     Overview 
     Embodiments of the invention are extremely simple to implement and do not require any additional solver software. Instead of using simple equations for the design constraints, the constraints are formulated as mathematical sets. These sets are used in conjunction with mathematical projections and fixed-point methods to find solutions. Such solutions can be found in a few hundred iterations, and every iteration is very fast to execute. The parallel nature of the fixed-point method allows for the potential use of GPU (Graphics Processing Unit) resources, which may render the processing extremely fast. Such processing is important in the context of horizontal roadway optimization, where finding feasible profiles may occur millions of times within a single optimization run. 
     A road profile can be drawn as a curve that consists of piecewise connected lines. In computer graphics and mathematics, such a curve is called a spline. The spline can be defined by the intersection points of these lines (i.e., a series of connected points). In road design, these points are called Points of Vertical Intersection (PVI). In addition, embodiments of the invention may utilize ground points instead of PVIs. 
     Design constraints are formulated with mathematical equations that use the positions of the connected points as variables. These equations divide the feasible positions into four mathematical sets, where each set represents one of the constraints. Mathematical projections are then used. A graphical projection in CAD is the process where one projects a three dimensional object on a two dimensional surface. A mathematical projection is a generalization of such a process. A mathematical projection is a mapping of one or multiple variables onto a set. In fact, a mathematical projection provides the point that is nearest in the set to the given variables. 
     Embodiments of the invention obtain/acquire a spline (e.g., a CAD user may provide an existing spline through a list of PVIs). By formulating the constraints as sets, the spline is projected on each constraint set individually. However, if the spline profile is projected onto the constraint set that represents one constraint, the resulting/modified spline may not satisfy the other constraints (i.e., in a design constraint set). 
     Embodiments of the invention utilize an alternating fixed-point method that projects a variable onto the first constraint. It then uses the result and projects it onto the second constraint. It then projects from the second constraint to the third constraint, and proceeds through all of the constraints in a constraint set. The method then starts the next iteration where it projects onto the first set again, etc. If the constraints have certain mathematical properties, then the method will reach/converge on a solution that satisfies all the constraints after a number of iterations. Besides the alternating method, there are many other fixed-point methods to find a solution (parallel, Douglas-Rachford, etc.) that may be used in accordance with embodiments of the invention (e.g., see ‘Convex Analysis and Monotone Operator Theory in Hilber Spaces’ by Heinz Bauschke and Patrick Combettes (Springer, 2011), which is incorporated by reference herein. 
     Embodiments of the invention utilize constraint formulations together with some carefully selected fixed-point algorithms to try and convert the given spline (e.g., road profile) into a modified spline that satisfies the design constraints. Most splines such as road profiles may be converted in a few hundred iterations, and have the resulting spline/road as close as possible to the original one. In some cases, the method is not able to find a solution immediately. With the help of error analysis, the method may suggest (but does not guarantee) to the user that there is no feasible solution for the given constraints. In such a case, a designer will then adapt the constraints or the existing spline/road profile. 
     Hardware Environment 
       FIG. 1  is an exemplary hardware and software environment  100  used to implement one or more embodiments of the invention. The hardware and software environment includes a computer  102  and may include peripherals. Computer  102  may be a user/client computer, server computer, or may be a database computer. The computer  102  comprises a general purpose hardware processor  104 A and/or a special purpose hardware processor  104 B (hereinafter alternatively collectively referred to as processor  104 ) and a memory  106 , such as random access memory (RAM). The computer  102  may be coupled to, and/or integrated with, other devices, including input/output (I/O) devices such as a keyboard  114 , a cursor control device  116  (e.g., a mouse, a pointing device, pen and tablet, touch screen, multi-touch device, etc.) and a printer  128 . In one or more embodiments, computer  102  may be coupled to, or may comprise, a portable or media viewing/listening device  132  (e.g., an MP3 player, iPod™, Nook™, portable digital video player, cellular device, personal digital assistant, etc.). In yet another embodiment, the computer  102  may comprise a multi-touch device, mobile phone, gaming system, internet enabled television, television set top box, or other internet enabled device executing on various platforms and operating systems. 
     In one embodiment, the computer  102  operates by the general purpose processor  104 A performing instructions defined by the computer program  110  under control of an operating system  108 . The computer program  110  and/or the operating system  108  may be stored in the memory  106  and may interface with the user and/or other devices to accept input and commands and, based on such input and commands and the instructions defined by the computer program  110  and operating system  108 , to provide output and results. 
     Output/results may be presented on the display  122  or provided to another device for presentation or further processing or action. In one embodiment, the display  122  comprises a liquid crystal display (LCD) having a plurality of separately addressable liquid crystals. Alternatively, the display  122  may comprise a light emitting diode (LED) display having clusters of red, green and blue diodes driven together to form full-color pixels. Each liquid crystal or pixel of the display  122  changes to an opaque or translucent state to form a part of the image on the display in response to the data or information generated by the processor  104  from the application of the instructions of the computer program  110  and/or operating system  108  to the input and commands. The image may be provided through a graphical user interface (GUI) module  118 . Although the GUI module  118  is depicted as a separate module, the instructions performing the GUI functions can be resident or distributed in the operating system  108 , the computer program  110 , or implemented with special purpose memory and processors. 
     In one or more embodiments, the display  122  is integrated with/into the computer  102  and comprises a multi-touch device having a touch sensing surface (e.g., track pod or touch screen) with the ability to recognize the presence of two or more points of contact with the surface. Examples of multi-touch devices include mobile devices (e.g., iPhone™, Nexus S™, Droid™ devices, etc.), tablet computers (e.g., iPad™, HP Touchpad™), portable/handheld game/music/video player/console devices (e.g., iPod Touch™, MP3 players, Nintendo 3DS™, PlayStation Portable™, etc.), touch tables, and walls (e.g., where an image is projected through acrylic and/or glass, and the image is then backlit with LEDs). 
     Some or all of the operations performed by the computer  102  according to the computer program  110  instructions may be implemented in a special purpose processor  104 B. In this embodiment, some or all of the computer program  110  instructions may be implemented via firmware instructions stored in a read only memory (ROM), a programmable read only memory (PROM) or flash memory within the special purpose processor  104 B or in memory  106 . The special purpose processor  104 B may also be hardwired through circuit design to perform some or all of the operations to implement the present invention. Further, the special purpose processor  104 B may be a hybrid processor, which includes dedicated circuitry for performing a subset of functions, and other circuits for performing more general functions such as responding to computer program  110  instructions. In one embodiment, the special purpose processor  104 B is an application specific integrated circuit (ASIC). 
     The computer  102  may also implement a compiler  112  that allows an application or computer program  110  written in a programming language such as COBOL, Pascal, C++, FORTRAN, or other language to be translated into processor  104  readable code. Alternatively, the compiler  112  may be an interpreter that executes instructions/source code directly, translates source code into an intermediate representation that is executed, or that executes stored precompiled code. Such source code may be written in a variety of programming languages such as Java™, Perl™, Basic™, etc. After completion, the application or computer program  110  accesses and manipulates data accepted from I/O devices and stored in the memory  106  of the computer  102  using the relationships and logic that were generated using the compiler  112 . 
     The computer  102  also optionally comprises an external communication device such as a modem, satellite link, Ethernet card, or other device for accepting input from, and providing output to, other computers  102 . 
     In one embodiment, instructions implementing the operating system  108 , the computer program  110 , and the compiler  112  are tangibly embodied in a non-transient computer-readable medium, e.g., data storage device  120 , which could include one or more fixed or removable data storage devices, such as a zip drive, floppy disc drive  124 , hard drive, CD-ROM drive, tape drive, etc. Further, the operating system  108  and the computer program  110  are comprised of computer program  110  instructions which, when accessed, read and executed by the computer  102 , cause the computer  102  to perform the steps necessary to implement and/or use the present invention or to load the program of instructions into a memory  106 , thus creating a special purpose data structure causing the computer  102  to operate as a specially programmed computer executing the method steps described herein. Computer program  110  and/or operating instructions may also be tangibly embodied in memory  106  and/or data communications devices  130 , thereby making a computer program product or article of manufacture according to the invention. As such, the terms “article of manufacture,” “program storage device,” and “computer program product,” as used herein, are intended to encompass a computer program accessible from any computer readable device or media. 
     Of course, those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with the computer  102 . 
       FIG. 2  schematically illustrates a typical distributed computer system  200  using a network  204  to connect client computers  202  to server computers  206 . A typical combination of resources may include a network  204  comprising the Internet, LANs (local area networks), WANs (wide area networks), SNA (systems network architecture) networks, or the like, clients  202  that are personal computers or workstations (as set forth in  FIG. 1 ), and servers  206  that are personal computers, workstations, minicomputers, or mainframes (as set forth in  FIG. 1 ). However, it may be noted that different networks such as a cellular network (e.g., GSM [global system for mobile communications] or otherwise), a satellite based network, or any other type of network may be used to connect clients  202  and servers  206  in accordance with embodiments of the invention. 
     A network  204  such as the Internet connects clients  202  to server computers  206 . Network  204  may utilize ethernet, coaxial cable, wireless communications, radio frequency (RF), etc. to connect and provide the communication between clients  202  and servers  206 . Clients  202  may execute a client application or web browser and communicate with server computers  206  executing web servers  210 . Such a web browser is typically a program such as MICROSOFT INTERNET EXPLORER™, MOZILLA FIREFOX™, OPERA™, APPLE SAFARI™, GOOGLE CHROME™, etc. Further, the software executing on clients  202  may be downloaded from server computer  206  to client computers  202  and installed as a plug-in or ACTIVEX™ control of a web browser. Accordingly, clients  202  may utilize ACTIVEX™ components/component object model (COM) or distributed COM (DCOM) components to provide a user interface on a display of client  202 . The web server  210  is typically a program such as MICROSOFT&#39;S INTERNET INFORMATION SERVER™. 
     Web server  210  may host an Active Server Page (ASP) or Internet Server Application Programming Interface (ISAPI) application  212 , which may be executing scripts. The scripts invoke objects that execute business logic (referred to as business objects). The business objects then manipulate data in database  216  through a database management system (DBMS)  214 . Alternatively, database  216  may be part of, or connected directly to, client  202  instead of communicating/obtaining the information from database  216  across network  204 . When a developer encapsulates the business functionality into objects, the system may be referred to as a component object model (COM) system. Accordingly, the scripts executing on web server  210  (and/or application  212 ) invoke COM objects that implement the business logic. Further, server  206  may utilize MICROSOFT′S™ Transaction Server (MTS) to access required data stored in database  216  via an interface such as ADO (Active Data Objects), OLE DB (Object Linking and Embedding DataBase), or ODBC (Open DataBase Connectivity). 
     Generally, these components  200 - 216  all comprise logic and/or data that is embodied in/or retrievable from device, medium, signal, or carrier, e.g., a data storage device, a data communications device, a remote computer or device coupled to the computer via a network or via another data communications device, etc. Moreover, this logic and/or data, when read, executed, and/or interpreted, results in the steps necessary to implement and/or use the present invention being performed. 
     Although the terms “user computer”, “client computer”, and/or “server computer” are referred to herein, it is understood that such computers  202  and  206  may be interchangeable and may further include thin client devices with limited or full processing capabilities, portable devices such as cell phones, notebook computers, pocket computers, multi-touch devices, and/or any other devices with suitable processing, communication, and input/output capability. 
     Of course, those skilled in the art will recognize that any combination of the above components, or any number of different components, peripherals, and other devices, may be used with computers  202  and  206 . 
     Embodiments of the invention are implemented as a software application on a client  202  or server computer  206 . Further, as described above, the client  202  or server computer  206  may comprise a thin client device or a portable device that has a multi-touch-based display. 
     Overview 
     Abstract Formulation of the Problem 
     One may assume that n∈{2, 3, . . . } and that
 
 X=     n  with standard inner product  •,•  and induced norm ∥•∥.  (1)
 
     One may also assume n strictly increasing breakpoints are given on the real line:
 
 t =( t   1   , . . . ,t   n )∈ X  such that  t   1   &lt; . . . &lt;t   n .  (2)
 
     The goal is to
 
find a vector  x =( x   1   , . . . ,x   n )∈ X   (3)
 
such that
 
( t   1   ,x   1 ), . . . ,( t   n   ,x   n ) satisfies a given set of constraints.  (4)
 
     Note that for every x∈X, the pair (t,x)∈X×X induces a corresponding piecewise linear function (linear spline) 
                         f     (     t   ,   x     )       ⁢       :     ⁢           [       t   1     ,     t   n       ]       →     ℝ   ⁢     :     ⁢           ⁢   τ     ↦       x   i     +       (       x     i   +   1       -     x   i       )     ⁢       τ   -     t   i           t     i   +   1       -     t   i               ,           (   5   )               
where τ∈[t i ,t i+1 ] and i∈{1, . . . , n−1}, which passes through the points {(t i ,x i )∈   2 |i∈I}. The set of constraints mentioned in (4) will involve the function ƒ (t,x) . Several types of constraints may be used within a design constraint set:
         interpolation constraints: For a given subset I of {1, . . . , n}, the entries x i  are prescribed: (∀i∈I)ƒ (t,x) (t i )=y i . This is an interpolation problem for the points {(t i ,y i )∈   2 |i∈I}.   slope constraints: For a given subset I of {1, . . . , n−1} and for every i∈I, the slope       

                     s   i     :=         x     i   +   1       -     x   i           t     i   +   1       -     t   i                 (   6   )               
of ƒ (t,x) | [t     i     ,t     i+1     ]  must lie in a given subset of  .
         curvature constraints: For a given subset I of {1, . . . , n−2} and for every i∈I, |s i+1 −s i |, the distance between the slopes s i  and s i+1  of two adjacent intervals [t i ,t i+1 ] and [t i+1 ,t i+2 ], must lie in a given subset of  .       

     Exemplary Instance in Road Design 
     The problem (e.g., equations (3)-(4)) introduced above and its solutions have several direct applications in engineering and computer-assisted design. For instance, an engineer may want to verify the feasibility of a design, or adapt the design according to the constraints. Examples drawn from Computer-Assisted Design (CAD) include designs for roadway profiles, pipe layouts, fuel lines in automotive designs such as cars and airplanes, overhead power lines, chairlifts, cable cars, and duct networks. 
     As described above, it is desirable to automate the design of road alignments. A road alignment is represented by the centerline of the road, which is idealized as a (generally) nonlinear, smooth curve in    3 . To facilitate construction drawings, civil engineers reduce the three-dimensional road design to two two-dimensional parts, horizontal and vertical. 
     The horizontal alignment is the plan (or map) view of the road.  FIG. 3  illustrates the vertical profiles of a ground profile g, initial road design ƒ (t,v) , and final road design ƒ (t,w)  for a highway design near Kelowna, B.C., Canada in accordance with one or more embodiments of the invention. In the vertical view, the ground profile g: [t 1 ,t n ]→  provides the elevation values of the existing ground along the centerline (see the dashed curve in  FIG. 3 ). Since earthwork operations such as cuts and fills are expensive items in road construction, a civil engineer tries to find a road profile represented by a linear spline ƒ (t,x)  that follows g as closely as possible. 
     In  FIG. 3 , the solution was found with a particular projection method called Dykstra&#39;s method, using a design speed of 130 km/h, and a maximum slope of 4%. (These engineering constraints translate into a specific set of slope and interpolation constraints.) 
     Design constraints imposed on ƒ (t,x)  by the engineer or by civil design standards such as those published by the American Association of State Highway and Transportation Officials (AASHTO) [1] include the following:
         At a certain station t i , the engineer may have to fix the elevation x i  to allow for construction of an intersection with an existing road that crosses the new road at t i . This corresponds to the (mathematically affine) interpolation constraint described above.   For safety reasons and to ensure good traffic flow, AASHTO requires that the slope between two stations t i  and t i+1  is bounded above and below. These are the (mathematically convex) slope constraints described above.   In a road profile, engineers fit a (usually parabolic) curve at the point of intersection of two line segments. The curvature depends on the grade change of the line segments and influences the vertical acceleration of a vehicle, as well as the stopping sight distance. AASHTO requires bounds on the slope change. This corresponds to the (mathematically convex) curvature constraint described above.   In some cases, the engineer requires a minimum drainage grade to allow flow and avoid catchment of storm water. These (mathematically challenging nonconvex) slope constraints are discussed in further detail below.       

     The starting spline for a road profile (see the dotted curve in  FIG. 3 ) may be denoted by:
 
ƒ (t,v) , where  t =( t   1   , . . . ,t   n )∈ X  and  v =( v   1   , . . . ,v   n )∈ X.   (7)
 
     In practice, the starting spline could simply be the connected line segments for the interpolation constraint, or it could be generated from the ground profile g by using Bellman&#39;s method (see [3] and [5] for details). In either case, one may assume that t is given and fixed, and that one needs to decide whether or not ƒ (t,v)  is feasible with respect to the aforementioned constraints. If v leads to a feasible spline, then the process id complete; otherwise, w∈X should be found such that the new road spline ƒ (t,w)  (see the solid line in  FIG. 3 ) satisfies the design constraints. Ideally, ƒ (t,w)  is close to the ground profile represented by (t, v). Finally, if there is no w∈X making the problem feasible, then such a condition should be detected through some suitable measure. 
     In view of the above, there are numerous constraints that may create obstacles in the context of road design. Fortunately, the constraints have sufficient structure can be taken advantage of and it may be demonstrated that the constraints parallelize which allows the problems/obstacles to be reduced to six constraint sets, each of which admits a closed form projection formula. These projections can then be used in conjunction with projection methods to solve the underlying feasibility problem. 
     Constraints and Projection Operators 
     Projection onto a General Convex Set 
     In this section, the constraints encountered in road design are made mathematically precise. Almost all of these constraints turn out to lead to sets that are convex and closed. Recall that a set C is convex if it contains all line segments between each pair taken from C:
 
(∀ c   0   ∈C )(∀ c   1   ∈C )(∀λ∈[0,1])(1−λ) c   0   +λc   1   ∈C.   (8)
 
     If C is a nonempty closed convex subset of X, then for every x∈X, the optimization problem 
                       d   ⁡     (     x   ,   C     )       :=       min     c   ∈   C       ⁢          x   -   c              ,           (   9   )               
which concerns the computation of the distance d(x,C) from x to the set C, has a unique solution, denoted by P C x and is called the projection of x onto C. The vector P C x is characterized by two properties, namely
 
 P   C   x∈C  and (∀ c∈C )   c−P   C   x,x−P   C   x ) ≦0.  (10)
 
     The induced operator P C :X→C is the projection operator or projector onto C. There are several examples that allow one to write down the projector in closed form or to approximate P C  provided C is the intersection of finitely many simple closed convex sets (see, e.g., [2, Chapters 28 and 29]). In a road design application, it is fortunately possible to obtain explicit formulas. As described below, these formulas may be made as convenient as possible for software implementation. Such formulas may be obtained for each of the three types of constraints. 
     Interpolation Constraints 
     It may be assumed that I is a set such that
 
{1 ,n} ⊂ I ⊂ { 1,2 , . . . ,n }, and  y =( y   i )∈   I   (11)
 
is given. Set
 
 Y:={x =( x   1   , . . . ,x   n )∈ X |(∀ i∈I ) x   i   =y   i }.  (12)
 
     The closed set Y is an affine subspace, i.e., (∀y∈Y)(∀z∈Y)(∀λ∈ )(1−λ)y+λz∈Y; in particular, Y is convex. For convenience, the explicit formula for the projection onto Y may be recorded. 
     Interpolation Constraint Projector Proposition 
     The projector onto Y is given by 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       Y 
                     
                     ⁢ 
                     
                       : 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     X 
                   
                   → 
                   X 
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       ( 
                       
                         
                           x 
                           1 
                         
                         , 
                         
                           x 
                           2 
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           x 
                           n 
                         
                       
                       ) 
                     
                     ↦ 
                     
                       ( 
                       
                         
                           c 
                           1 
                         
                         , 
                         
                           c 
                           2 
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           c 
                           n 
                         
                       
                       ) 
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       where 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         c 
                         i 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 y 
                                 i 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                 
                                 ∈ 
                                 I 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 i 
                               
                               , 
                             
                           
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                               
                               ∉ 
                               
                                 I 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     Slope Constraints 
     One may start with a simple special case that will also be useful in handling general slope constraints. To this end, let i∈{1, 2, . . . , n−1}. The constraint set S i  imposes that the absolute value of the slope ƒ (t,x)  for the interval [t i ,t i+1 ] is bounded above, i.e., there exists α i ≧0 such that
 
 S   i   :={x =( x   1   , . . . ,x   n )∈   n   ∥x   i+1   −x   i |≦α i }  (15)
 
     Indeed, if the actual maximum absolute slope is σ i ≧0, then, setting α i =σ i |t i+1 −t i |, one may note that 
                                x     i   +   1       -     x   i           t     i   +   1       -     t   i              ≤     σ   i       ⇔              x     i   +   1       -     x   i            ≤     α   i       ⇔       ±     (       x     i   +   1       -     x   i       )       ≤       α   i     .               (   16   )               ⇔       ±     (         e     i   +   1       -     e   i       ,   x     )       ≤     α   i               (   17   )                 ⇔       -     α   i       ≤     〈         e     i   +   1       -     e   i       ,   x     )     ≤     α   i         ,           (   18   )               
where e i  and e i+1  denote the standard unit vectors in X (with the number 1 in position i and i+1, respectively, and zeros elsewhere). The last characterization reveals that S i  is the intersection of two halfspaces whose boundary hyperplanes are orthogonal to e i+1 −e i . In particular, S i  is a closed convex subset of X. Using e.g., [2, Example 28.17], one obtains for every x∈X,
 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       
                         S 
                         i 
                       
                     
                     ⁢ 
                     x 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               x 
                               + 
                               
                                 
                                   
                                     
                                       - 
                                       
                                         α 
                                         i 
                                       
                                     
                                     - 
                                     
                                       〈 
                                       
                                         
                                           
                                             e 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             e 
                                             i 
                                           
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                   
                                   
                                     
                                        
                                       
                                         
                                           e 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         - 
                                         
                                           e 
                                           i 
                                         
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       e 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       e 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   〈 
                                   
                                     
                                       
                                         e 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         e 
                                         i 
                                       
                                     
                                     , 
                                     x 
                                   
                                   ) 
                                 
                               
                               &lt; 
                               
                                 - 
                                 
                                   α 
                                   i 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             x 
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 - 
                                 
                                   α 
                                   i 
                                 
                               
                               ≤ 
                               
                                 〈 
                                 
                                   
                                     
                                       e 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       e 
                                       i 
                                     
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                               ≤ 
                               
                                 α 
                                 i 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               x 
                               + 
                               
                                 
                                   
                                     
                                       α 
                                       i 
                                     
                                     - 
                                     
                                       〈 
                                       
                                         
                                           
                                             e 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             e 
                                             i 
                                           
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                   
                                   
                                     
                                        
                                       
                                         
                                           e 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         - 
                                         
                                           e 
                                           i 
                                         
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       e 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       e 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 〈 
                                 
                                   
                                     
                                       e 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       e 
                                       i 
                                     
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                             
                             &gt; 
                             
                               
                                 α 
                                 i 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
     This formula shows that (P S     i   x) j =x j , for every j∈I\{i,i+1}. Thus, the only entries that possibly change after executing P S     i    are in positions i and i+1. After some simplification, one obtains for these entries the formula: 
     
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         
                           ( 
                           
                             
                               P 
                               
                                 S 
                                 i 
                               
                             
                             ⁢ 
                             x 
                           
                           ) 
                         
                         i 
                       
                       , 
                       
                         
                           ( 
                           
                             
                               P 
                               
                                 S 
                                 i 
                               
                             
                             ⁢ 
                             x 
                           
                           ) 
                         
                         
                           i 
                           + 
                           1 
                         
                       
                     
                     ) 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     + 
                                     
                                       α 
                                       i 
                                     
                                   
                                   , 
                                   
                                     
                                       x 
                                       
                                         i 
                                         ⁢ 
                                         
                                             
                                         
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       α 
                                       i 
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 - 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               &gt; 
                               
                                 α 
                                 i 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 , 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                    
                                   
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       x 
                                       i 
                                     
                                   
                                    
                                 
                               
                               ≤ 
                               
                                 α 
                                 i 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       α 
                                       i 
                                     
                                   
                                   , 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     + 
                                     
                                       α 
                                       i 
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               - 
                               
                                 x 
                                 i 
                               
                             
                             &gt; 
                             
                               
                                 α 
                                 i 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
     It may be noted that
 
 x∉S   i   ( P   S     i     x ) i   ≠x   i  and ( P   S     i     x ) i+1   ≠x   i+1 ;  (21)
 
     Furthermore, if α i =+∞, i.e., no slope constraint, then (20) is valid as well. 
     Now one may examine the general case. The existence of a vector a=(α i )∈   +   n−1  is assumed such that the constraint set is:
 
 S=∩   i∈{1, . . . ,n−1}   S   i ={( x   1   , . . . ,x   n )∈   n |(∀ i∈{ 1, . . . , n− 1})| x   i+1   −x   i |≦α i },   (22)
 
where S i  is defined in (15). While an explicit formula is obtained to deal with a single slope constraint (see (20)), one is unaware of a corresponding formula for P S . Furthermore, since P S     i   , possibly modifies the vector in positions i and i+1 (but not elsewhere), one cannot use (20) for the sets S i  and S i+1  concurrently because their projections possibly modify positions (i, i+1) and (i+1, i+2) (see (21)), but not necessarily in a consistent manner at position i+1. However, by combining the n−1 slope constraints according to parity of indices, i.e., by setting
 
 S   even   :=∩     S   i , and  S   odd   :=∩     S   i ,  (23)
 
one may see that
 
 S=S   even   ∩S   odd   (24)
 
can be written as the intersection of just two constraint sets. Furthermore, (20) yields the fully parallel update formulas:
 
     Convex Slope Constraint Projector Proposition 
     For every x∈X, the projectors onto S even  and S odd  are given by
 
 P   S     even     x =( x   1 ,( P   S     2     x ) 2 ,( P   S     2     ,x ) 3 ,( P   S     4     x ) 4 ,( P   S     4     x ) 5 , . . . )∈ X,   (25)
 
where the last entry in (25) is x n  if n is even; and
 
 P   S     odd     x =(( P   S     1     x ) 1 ,( P   S     1     x ) 2 ,( P   S     3     ,x ) 3 ,( P   S     3     x ) 4 , . . . )∈ X,   (26)
 
where the last entry in (26) is x n  if n is odd.
 
     The constraints making up the aggregated slope constraint are very special polyhedra, namely “strips”, i.e., the intersection of two halfspaces with opposing normal vectors. This motivates the technique of not just projecting onto these sets but rather inside them: either one reflects into the strip, or (if the strip is too distant) the corresponding midpoint of the strip is jumped to. The formula for this operator may be recorded. 
     Intrepid Slope Constraint Projectors 
     The intrepid counterpart of (20), is (here sgn denotes the signum function) 
     
       
         
           
             
               
                 
                   
                     ( 
                     
                       
                         x 
                         i 
                       
                       , 
                       
                         x 
                         
                           i 
                           + 
                           1 
                         
                       
                     
                     ) 
                   
                   ↦ 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                   
                                   , 
                                   
                                     
                                       x 
                                       
                                         i 
                                         ⁢ 
                                         
                                             
                                         
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                    
                                   
                                     
                                       x 
                                       i 
                                     
                                     - 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                   
                                    
                                 
                               
                               &gt; 
                               
                                 2 
                                 ⁢ 
                                 
                                   α 
                                   i 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 , 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                    
                                   
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       x 
                                       i 
                                     
                                   
                                    
                                 
                               
                               ≤ 
                               
                                 α 
                                 i 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 , 
                                 
                                   x 
                                   i 
                                 
                               
                               ) 
                             
                             + 
                             
                               
                                 sgn 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     - 
                                     
                                       x 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     - 
                                     
                                       α 
                                       i 
                                     
                                   
                                   , 
                                   
                                     α 
                                     i 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 α 
                                 i 
                               
                             
                             &lt; 
                             
                                
                               
                                 
                                   x 
                                   i 
                                 
                                 - 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                                
                             
                             &lt; 
                             
                               2 
                               ⁢ 
                               
                                 
                                   α 
                                   i 
                                 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
           
         
       
     
     These operators lead to the intrepid counterpart of (2.2). 
     Curvature Constraints 
     Again, a simple special case is explained first that will also be useful in handling the general curvature constraints. To this end, let i∈{1, . . . , n−2}. The constraint requires that the difference of consecutive slopes is bounded above and below. Hence there exists γ i ∈  and δ i ∈  such that γ i ≧δ i  and 
     
       
         
           
             
               
                 
                   
                     C 
                     i 
                   
                   := 
                   
                     
                       { 
                       
                         x 
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   1 
                                 
                                 , 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                                 
                                   x 
                                   n 
                                 
                               
                               ) 
                             
                             ∈ 
                             
                               ℝ 
                               n 
                             
                           
                           | 
                           
                             
                               γ 
                               i 
                             
                             ≥ 
                             
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       2 
                                     
                                   
                                   - 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                                 
                                   
                                     t 
                                     
                                       i 
                                       + 
                                       2 
                                     
                                   
                                   - 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                               
                               - 
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   - 
                                   
                                     x 
                                     i 
                                   
                                 
                                 
                                   
                                     t 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   - 
                                   
                                     t 
                                     i 
                                   
                                 
                               
                             
                             ≥ 
                             
                               δ 
                               i 
                             
                           
                         
                       
                       } 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     Set
 
τ i   :=t   i+1   −t   i , τ i+1   :=t   i+2   −t   i+1 , and  u   i :=τ i+1   e   i −(τ i +τ i+1 ) e   i+1 +τ i   e   i+2 .   (29)
 
     Then τ i &gt;0, τ 1+1 &gt;0, and for every x∈X,
 
 x∈C   i   γ i τ i+1 τ i   ≧     u   i   ,x     ≧δ   i τ i+1 τ i .  (30)
 
     Again, one may note that C i  is a closed convex polyhedron and by e.g. [2, Example 28.17], one obtains: 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       
                         C 
                         i 
                       
                     
                     ⁢ 
                     
                       : 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     x 
                   
                   ↦ 
                   
                     { 
                     
                       
                         
                           
                             
                               x 
                               + 
                               
                                 
                                   
                                     
                                       
                                         δ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                     - 
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   〈 
                                   
                                     
                                       u 
                                       i 
                                     
                                     , 
                                     x 
                                   
                                   〉 
                                 
                               
                               &lt; 
                               
                                 
                                   δ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             x 
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   δ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ≤ 
                               
                                 〈 
                                 
                                   
                                     u 
                                     i 
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                               ≤ 
                               
                                 
                                   γ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               x 
                               + 
                               
                                 
                                   
                                     
                                       
                                         γ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                     - 
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 γ 
                                 i 
                               
                               ⁢ 
                               
                                 τ 
                                 i 
                               
                               ⁢ 
                               
                                 τ 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                             
                             &lt; 
                             
                               
                                 〈 
                                 
                                   
                                     u 
                                     i 
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
           
         
       
     
     Since u i ∈span{e i ,e i+1 ,e i+2 }, it follows that
 
{ j∈{ 1 , . . . ,n}|x   j ≠( P   C     i     x ) j } ⊂ { i,i+ 1 ,i+ 2}.  (32)
 
     One may now turn to the general curvature constraints. One assumes the existence of a vector c=(γ i )∈   n−2  and d=(δ i )∈   n−2  such that the constraint set is 
     
       
         
           
             
               
                 
                   
                     
                       
                         C 
                         = 
                           
                         ⁢ 
                         
                           
                             ⋂ 
                             
                               i 
                               ∈ 
                               
                                 { 
                                 
                                   1 
                                   , 
                                   … 
                                   ⁢ 
                                   
                                       
                                   
                                   , 
                                   
                                     n 
                                     - 
                                     2 
                                   
                                 
                                 } 
                               
                             
                           
                           ⁢ 
                           
                             C 
                             i 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             { 
                             
                               
                                 
                                   
                                     
                                       
                                         ( 
                                         
                                           
                                             x 
                                             1 
                                           
                                           , 
                                           … 
                                           ⁢ 
                                           
                                               
                                           
                                           , 
                                           
                                             x 
                                             n 
                                           
                                         
                                         ) 
                                       
                                       ∈ 
                                       X 
                                     
                                     ❘ 
                                     
                                       
                                         
                                           ( 
                                           
                                             ∀ 
                                             
                                               i 
                                               ∈ 
                                               
                                                 { 
                                                 
                                                   1 
                                                   , 
                                                   … 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   , 
                                                   
                                                     n 
                                                     - 
                                                     2 
                                                   
                                                 
                                                 } 
                                               
                                             
                                           
                                           ) 
                                         
                                         ⁢ 
                                         
                                           γ 
                                           i 
                                         
                                       
                                       ≥ 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               2 
                                             
                                           
                                           - 
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                         
                                         
                                           
                                             t 
                                             
                                               i 
                                               + 
                                               2 
                                             
                                           
                                           - 
                                           
                                             t 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                         
                                       
                                       - 
                                       
                                         
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             x 
                                             i 
                                           
                                         
                                         
                                           
                                             t 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             t 
                                             i 
                                           
                                         
                                       
                                     
                                     ≥ 
                                     
                                       δ 
                                       i 
                                     
                                   
                                 
                               
                             
                             } 
                           
                           . 
                           
                             ( 
                             34 
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   33 
                   ) 
                 
               
             
           
         
       
     
     Because of (32), these n−2 constraints may be aggregated into three constraint sets that allow projections in closed form. To this end, one sets:
 
(∀ j∈{ 1,2,3}) C   [j]   :=∩     C   i   (35)
 
so that
 
 C=C   [1]   ∩C   [2]   ∩C   [3] .  (36)
 
Combined with (31), one obtains the following.
 
     Curvature Constraint Projector Proposition 
     For every x∈X, the projectors onto C [1] , C [2] , and C [3]  are given
 
 P   C     [1]     x =(( P   C     1     x ) i ,( P   C     1     x ) 2 ,( P   C     1     x ) 3 ,( P   C     4     x ) 4 ,( P   C     4     x ) 5 ,( P   C     4     x ) 6 , . . . ),  (37)
 
 P   C     [2]     x =( x   1 ,( P   C     2     x ) 2 ,( P   C     2     ,x ) 3 ,( P   C     2     x ) 4 ,( P   C     5     ,x ) 5 ,( P   C     5     x ) 6 ,( P   C     5     x ) 7 , . . . ),  (38)
 
 P   C     [3]     x =( x   1   ,x   2 ,( P   C     3     x ) 3 ,( P   C     3     x ) 4 ,( P   C     3     x ) 5 ,( P   C     6     x ) 6 ,( P   C     6     x ) 7 ,( P   C     6     x ) 8 , . . . ),  (39)
 
respectively, where each P C     i    is given by (31).
 
     The intrepid counterpart can then be recorded. 
     Intrepid Curvature Constraint Projectors Proposition 
     The intrepid counterpart of (31) is 
     
       
         
           
             
               
                 
                   x 
                   ↦ 
                   
                     { 
                     
                       
                         
                           
                             
                               x 
                               - 
                               
                                 
                                   
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                     - 
                                     
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         
                                           
                                             τ 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           ⁡ 
                                           
                                             ( 
                                             
                                               
                                                 δ 
                                                 i 
                                               
                                               + 
                                               
                                                 γ 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                         / 
                                         2 
                                       
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     〈 
                                     
                                       
                                         u 
                                         i 
                                       
                                       , 
                                       x 
                                     
                                     〉 
                                   
                                 
                                 &lt; 
                                 
                                   
                                     τ 
                                     i 
                                   
                                   ⁢ 
                                   
                                     
                                       
                                         τ 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             3 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             
                                               δ 
                                               i 
                                             
                                           
                                           - 
                                           
                                             γ 
                                             i 
                                           
                                         
                                         ) 
                                       
                                     
                                     / 
                                     2 
                                   
                                 
                               
                               ; 
                             
                             ⁢ 
                             
                                 
                             
                           
                         
                       
                       
                         
                           
                             
                               x 
                               - 
                               
                                 2 
                                 ⁢ 
                                 
                                   
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                     - 
                                     
                                       
                                         δ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       τ 
                                       i 
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           τ 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           
                                             
                                               3 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               
                                                 δ 
                                                 i 
                                               
                                             
                                             - 
                                             
                                               γ 
                                               i 
                                             
                                           
                                           ) 
                                         
                                       
                                       / 
                                       2 
                                     
                                   
                                   ≤ 
                                 
                               
                             
                             
                               
                                 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     
                                       
                                         〈 
                                         
                                           
                                             u 
                                             i 
                                           
                                           , 
                                           x 
                                         
                                         〉 
                                       
                                       &lt; 
                                       
                                         
                                           δ 
                                           i 
                                         
                                         ⁢ 
                                         
                                           τ 
                                           i 
                                         
                                         ⁢ 
                                         
                                           τ 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                       
                                     
                                     ; 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             x 
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   δ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ≤ 
                               
                                 〈 
                                 
                                   
                                     u 
                                     i 
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                               ≤ 
                               
                                 
                                   γ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   i 
                                 
                                 ⁢ 
                                 
                                   τ 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               x 
                               - 
                               
                                 2 
                                 ⁢ 
                                 
                                   
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                     - 
                                     
                                       
                                         γ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         τ 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       γ 
                                       i 
                                     
                                     ⁢ 
                                     
                                       τ 
                                       i 
                                     
                                     ⁢ 
                                     
                                       τ 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                   
                                   &lt; 
                                   
                                     〈 
                                     
                                       
                                         u 
                                         i 
                                       
                                       , 
                                       x 
                                     
                                     〉 
                                   
                                   ≤ 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       τ 
                                       i 
                                     
                                     ⁢ 
                                     
                                       
                                         
                                           τ 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         ⁡ 
                                         
                                           ( 
                                           
                                             
                                               3 
                                               ⁢ 
                                               
                                                   
                                               
                                               ⁢ 
                                               
                                                 γ 
                                                 i 
                                               
                                             
                                             - 
                                             
                                               δ 
                                               i 
                                             
                                           
                                           ) 
                                         
                                       
                                       / 
                                       2 
                                     
                                   
                                   ; 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               x 
                               - 
                               
                                 
                                   
                                     
                                       〈 
                                       
                                         
                                           u 
                                           i 
                                         
                                         , 
                                         x 
                                       
                                       〉 
                                     
                                     - 
                                     
                                       
                                         τ 
                                         i 
                                       
                                       ⁢ 
                                       
                                         
                                           
                                             τ 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           ⁡ 
                                           
                                             ( 
                                             
                                               
                                                 δ 
                                                 i 
                                               
                                               + 
                                               
                                                 γ 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                         / 
                                         2 
                                       
                                     
                                   
                                   
                                     
                                        
                                       
                                         u 
                                         i 
                                       
                                        
                                     
                                     2 
                                   
                                 
                                 ⁢ 
                                 
                                   u 
                                   i 
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               if 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 τ 
                                 i 
                               
                               ⁢ 
                               
                                 
                                   
                                     τ 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         3 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           γ 
                                           i 
                                         
                                       
                                       - 
                                       
                                         δ 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                                 / 
                                 2 
                               
                             
                             &lt; 
                             
                               
                                 〈 
                                 
                                   
                                     u 
                                     i 
                                   
                                   , 
                                   x 
                                 
                                 〉 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   40 
                   ) 
                 
               
             
           
         
       
     
     These counterparts induce the intrepid variant of (37). 
     The Convex Feasibility Problem 
     The convex feasibility problem motivated by road design is to find a point in
 
 C:=Y∩S   even   ∩S   odd   ∩C   [1]   ∩C   [2]   ∩C   [3] ,  (41)
 
where the sets on the right side are defined in (12), (23), and (35). Note that explicit formulas are available for all six projectors (see the above propositions). Moreover, intrepid variants of the projectors onto the five constraint sets S even , S odd , C [1] , C [2] , and C [3]  are also available (e.g., see the above propositions). There is no fundamentally different intrepid variant of P Y  because the interior of the affine subspace Y is empty.
 
Feasibility Problems and Projection Methods
 
     In this section, a selection of projection methods for solving feasibility problems are presented. To this end, let m∈{2, 3, . . . } and C 1 , . . . , C m  be nonempty closed convex subsets of X. 
     The m-Set Feasibility Problem and its Reduction to Two Sets 
     The aim is to
 
find  x∈C:=C   1   ∩ . . . ∩C   m ≠∅,  (42)
 
or, even more ambitiously, to compute
 
 P   C   v   (43)
 
for some given point v∈X. Of course, one has the concrete scenario (41) described above, where m=6, in mind; however, the discussion in this section is not limited to that particular instance.
 
     Projection methods solve (42) by generating a sequence of vectors by using the projectors P C     1   , . . . , P C     m    onto the individual sets. As described above, these projectors are available for a variety of constraints appearing in practical applications. Before the algorithms are catalogued, it may be noted that some algorithms work intrinsically only with two constraint sets. Because m may not be large, this turns out to be not a handicap at all as one can reformulate (42) in a product space in the following fashion: In the Hilbert product space
 
 X:=X   m ,  (44)
 
equipped with
 
   x,y     =Σ   i=1   m     x   i   ,y   i    and ∥ x ∥=√{square root over (Σ i+1   m   ∥x   i ∥ 2 )},  (45)
 
where x=(x 1 , . . . , x m ) and y=(y 1 , . . . , y m ) belong to X, one considers the Cartesian product of the constraints together with the diagonal in X, i.e.,
 
 C:=C   1   × . . . ×C   m  and  D :={( x, . . . ,x )∈ X|x∈X}.   (46)
 
Then for every x∈X, the key equivalence is obtained:
 
 x∈C   ( x, . . . ,x )∈ C∩D;   (47)
 
thus, the original m-set feasibility problem (42) in X reduces to two-set feasibility problem for the sets C and D in X. This approach is viable because the projectors onto C and D are given explicitly by:
 
 P   C :( x   1   , . . . ,x   m ) ( P   C     1     x   1   , . . . ,P   C     m     x   m )  (48)
 
and by
 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           P 
                           D 
                         
                         ⁢ 
                         
                           : 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               x 
                               1 
                             
                             , 
                             … 
                             ⁢ 
                             
                                 
                             
                             , 
                             
                               x 
                               m 
                             
                           
                           ) 
                         
                       
                       ↦ 
                       
                         ( 
                         
                           y 
                           , 
                           … 
                           ⁢ 
                           
                               
                           
                           , 
                           y 
                         
                         ) 
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     where 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       y 
                       = 
                       
                         
                           1 
                           m 
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               x 
                               1 
                             
                             + 
                             … 
                             + 
                             
                               x 
                               m 
                             
                           
                           ) 
                         
                       
                     
                     , 
                   
                 
               
               
                 
                   
                     ( 
                     49 
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
     Exemplary Projection Methods 
     In this subsection, some examples of projection methods are described. Each of these methods produces a sequence that converges—sometimes after applying a suitable operator—to a point in C provided that C≠∅ (and perhaps an additional assumption is satisfied). 
     Note that numerous generalizations of projection methods may be known. However, such methods typically involve additional parameters (e.g., weights and relaxation parameters). 
     In embodiments of the invention, one can employ any projection method, or combinations, or compositions of projection methods. Only a small subset of all potential/possible projection methods are described herein. 
     While these methods are generally not able to find P C v, they may lead to feasible solutions that are “fairly close” to P C v provided the starting point is chosen to be v. 
     One exemplary projection method that may be used is that of cyclic projections. 
     Cyclic Projections (CycP)) 
     Set x 0 =v and update
 
(∀ k ∈ ) x   k+1   :=Tx   k , where  T:=P   C     m     P   C     m−1      . . . P   C     1   .  (50)
 
     A modern variant of CycP replaces the projectors in (50) by intrepid counterparts when available. 
     Cyclic Intrepid Projections (CycIP)) 
     Set x 0 =v and update
 
(∀ k ∈ ) x   k+1   :=Tx   k , where  T:=R   m   R   m−1    . . . R   1 ,  (51)
 
where each R i  is either an intrepid counterpart of P C     i    (if available), or P C     i    itself (if there is no intrepid counterpart).
 
     The next method is different from the previous ones in two aspects: First, it truly operates in X and thus has increased storage requirements—fortunately, m is small in an application of embodiments of the invention so this is of no concern when dealing with (41). Second, the sequence of interest is actually different and derived from another sequence that governs the iteration. 
     Douglas-Rachford (D-R) 
     Set x 0 =(v, . . . , v)∈X=X m . Given k∈  and x k =(x k,1 , . . . , x k,m )∈X, update to x k+1 =(x k+1,1 , . . . , x k+1,m ), where 
                       x   _     k     =       1   m     ⁢       ∑     i   =   1     m     ⁢           ⁢     x     k   ,   i                   (   52   )               
and
 
(∀ i∈{ 1 , . . . ,m }) x   k+1,i   =x   k,i   −x   k,i   − x     k   +P   C     i   (2   x     k   −x   k,i ).  (53)
 
     The sequence of interest is not (x k    but rather ( x   k   . 
     There are many other methods of this type (see, e.g., [2]); including Dykstra&#39;s method, parallel projections, and string-averaging projections. Often these methods have parameters that can be adjusted to improve the speed of convergence. 
     Nonconvexity 
     In this section, remarks are provided on the possible absence of convexity. 
     Nonconvex Slope Constraints 
     A case with nonconvex constraints is considered. This type of constraint does occur frequently in applications; however, convergence of the iterates is guaranteed at best only when the starting point is already sufficiently close to the set of solutions. The convex constraints described above are used with one crucial modification: The slope constraint (15) is tightened by additionally imposing a minimum absolute value slope, i.e., the existence of two vectors a=(α i ) and b=(β i ) in    +   n−1  are assumed such that
 
(∀ i∈I ) S   i   :={x =( x   1   , . . . ,x   n )∈   n |α i   ≧|x   i+1   −x   i |≧β i }.  (54)
 
     Note that if β i &gt;0, then S i  is not convex. Analogously to (22), these sets are aggregated to obtain the general nonconvex constraint set
 
 S=∩   i∈{1, . . . ,n−1}   S   i .  (55)
 
     Let i∈{1, . . . , n−1} and x∈X. The counterpart of (20) is obtained and it may be noted that P S     i   x is different from x at most in positions i and i+1, and ((P S     i   x) i , (P S     i   x) i+1 ) 
     
       
         
           
               
             
               
                 
                   
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   1 
                                   2 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       + 
                                       
                                         α 
                                         i 
                                       
                                     
                                     , 
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         α 
                                         i 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                                 &lt; 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     α 
                                     i 
                                   
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   , 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                                 ) 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       x 
                                       i 
                                     
                                   
                                   - 
                                   
                                     α 
                                     i 
                                   
                                 
                                 ≤ 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 ≤ 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     β 
                                     i 
                                   
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   1 
                                   2 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       + 
                                       
                                         β 
                                         i 
                                       
                                     
                                     , 
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         β 
                                         i 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       x 
                                       i 
                                     
                                   
                                   - 
                                   
                                     β 
                                     i 
                                   
                                 
                                 &lt; 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 ≤ 
                                 
                                   x 
                                   i 
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   1 
                                   2 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         β 
                                         i 
                                       
                                     
                                     , 
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       + 
                                       
                                         β 
                                         i 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 ≤ 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 &lt; 
                                 
                                   
                                     x 
                                     i 
                                   
                                   + 
                                   
                                     β 
                                     i 
                                   
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     x 
                                     i 
                                   
                                   , 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                 
                                 ) 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       x 
                                       i 
                                     
                                   
                                   + 
                                   
                                     β 
                                     i 
                                   
                                 
                                 ≤ 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 ≤ 
                                 
                                   
                                     x 
                                     i 
                                   
                                   + 
                                   
                                     α 
                                     i 
                                   
                                 
                               
                               ; 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   1 
                                   2 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       - 
                                       
                                         α 
                                         i 
                                       
                                     
                                     , 
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         x 
                                         
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       + 
                                       
                                         α 
                                         i 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 + 
                                 
                                   α 
                                   i 
                                 
                               
                               &lt; 
                               
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                                 . 
                               
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     ( 
                     56 
                     ) 
                   
                 
               
             
           
         
       
     
     This formula allows one to deal with the general case as described above. Thus, one may obtain the counterpart of the Convex Slope Constraint Projector Proposition described above. 
     The intrepid counterpart of (56) may be recorded: 
     
       
         
           
               
             
               
                 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         
                                           
                                             x 
                                             i 
                                           
                                           + 
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           + 
                                           
                                             
                                               1 
                                               2 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   α 
                                                   i 
                                                 
                                                 + 
                                                 
                                                   β 
                                                   i 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         , 
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           x 
                                           i 
                                         
                                         + 
                                         
                                           x 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         - 
                                         
                                           
                                             1 
                                             2 
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 α 
                                                 i 
                                               
                                               + 
                                               
                                                 β 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                   
                                   &lt; 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       ( 
                                       
                                         
                                           β 
                                           i 
                                         
                                         - 
                                         
                                           3 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             α 
                                             i 
                                           
                                         
                                       
                                       ) 
                                     
                                     / 
                                     2 
                                   
                                   ; 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   + 
                                   
                                     α 
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     α 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     
                                       if 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         x 
                                         i 
                                       
                                     
                                     + 
                                     
                                       
                                         ( 
                                         
                                           
                                             β 
                                             i 
                                           
                                           - 
                                           
                                             3 
                                             ⁢ 
                                             
                                                 
                                             
                                             ⁢ 
                                             
                                               α 
                                               i 
                                             
                                           
                                         
                                         ) 
                                       
                                       / 
                                       2 
                                     
                                   
                                   ≤ 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     &lt; 
                                     
                                       
                                         x 
                                         i 
                                       
                                       - 
                                       
                                         α 
                                         i 
                                       
                                     
                                   
                                   ; 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 , 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 - 
                                 
                                   α 
                                   i 
                                 
                               
                               ≤ 
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               ≤ 
                               
                                 
                                   x 
                                   i 
                                 
                                 - 
                                 
                                   β 
                                   i 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   + 
                                   
                                     β 
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     x 
                                     i 
                                   
                                   - 
                                   
                                     β 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     if 
                                     ⁢ 
                                     
                                         
                                     
                                     - 
                                     
                                       β 
                                       i 
                                     
                                   
                                   &lt; 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   ≤ 
                                   
                                     
                                       x 
                                       i 
                                     
                                     + 
                                   
                                 
                               
                             
                             
                               
                                 
                                   
                                     min 
                                     ⁢ 
                                     
                                       { 
                                       
                                         0 
                                         , 
                                         
                                           
                                             ( 
                                             
                                               
                                                 α 
                                                 i 
                                               
                                               - 
                                               
                                                 3 
                                                 ⁢ 
                                                 
                                                     
                                                 
                                                 ⁢ 
                                                 
                                                   β 
                                                   i 
                                                 
                                               
                                             
                                             ) 
                                           
                                           / 
                                           2 
                                         
                                       
                                       } 
                                     
                                   
                                   ; 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         
                                           
                                             x 
                                             i 
                                           
                                           + 
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           + 
                                           
                                             
                                               1 
                                               2 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   α 
                                                   i 
                                                 
                                                 + 
                                                 
                                                   β 
                                                   i 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         , 
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           x 
                                           i 
                                         
                                         + 
                                         
                                           x 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         - 
                                         
                                           
                                             1 
                                             2 
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 α 
                                                 i 
                                               
                                               + 
                                               
                                                 β 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 + 
                                 
                                   
                                     
                                       α 
                                       i 
                                     
                                     - 
                                     
                                       3 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         β 
                                         i 
                                       
                                     
                                   
                                   2 
                                 
                               
                               &lt; 
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               ≤ 
                               
                                 x 
                                 i 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         
                                           
                                             x 
                                             i 
                                           
                                           + 
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             
                                               1 
                                               2 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   α 
                                                   i 
                                                 
                                                 + 
                                                 
                                                   β 
                                                   i 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         , 
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           x 
                                           i 
                                         
                                         + 
                                         
                                           x 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         + 
                                         
                                           
                                             1 
                                             2 
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 α 
                                                 i 
                                               
                                               + 
                                               
                                                 β 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   x 
                                   i 
                                 
                               
                               &lt; 
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               ≤ 
                               
                                 
                                   x 
                                   i 
                                 
                                 + 
                                 
                                   
                                     
                                       3 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         β 
                                         i 
                                       
                                     
                                     - 
                                     
                                       α 
                                       i 
                                     
                                   
                                   2 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   - 
                                   
                                     β 
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     x 
                                     i 
                                   
                                   + 
                                   
                                     β 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   
                                     
                                       if 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         x 
                                         i 
                                       
                                     
                                     + 
                                     
                                       max 
                                       ⁢ 
                                       
                                         { 
                                         
                                           0 
                                           , 
                                           
                                             
                                               ( 
                                               
                                                 
                                                   3 
                                                   ⁢ 
                                                   
                                                       
                                                   
                                                   ⁢ 
                                                   
                                                     β 
                                                     i 
                                                   
                                                 
                                                 - 
                                                 
                                                   α 
                                                   i 
                                                 
                                               
                                               ) 
                                             
                                             / 
                                             2 
                                           
                                         
                                         } 
                                       
                                     
                                   
                                   ≤ 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       x 
                                       
                                         i 
                                         + 
                                         1 
                                       
                                     
                                     &lt; 
                                     
                                       
                                         x 
                                         i 
                                       
                                       + 
                                       
                                         β 
                                         i 
                                       
                                     
                                   
                                   ; 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   x 
                                   i 
                                 
                                 , 
                                 
                                   x 
                                   
                                     i 
                                     + 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 + 
                                 
                                   β 
                                   i 
                                 
                               
                               ≤ 
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               ≤ 
                               
                                 
                                   x 
                                   i 
                                 
                                 + 
                                 
                                   α 
                                   i 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     x 
                                     
                                       i 
                                       + 
                                       1 
                                     
                                   
                                   - 
                                   
                                     α 
                                     i 
                                   
                                 
                                 , 
                                 
                                   
                                     x 
                                     i 
                                   
                                   + 
                                   
                                     α 
                                     i 
                                   
                                 
                               
                               ) 
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 
                                   if 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     x 
                                     i 
                                   
                                 
                                 + 
                                 
                                   α 
                                   i 
                                 
                               
                               &lt; 
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               ≤ 
                               
                                 
                                   x 
                                   i 
                                 
                                 + 
                                 
                                   
                                     ( 
                                     
                                       
                                         3 
                                         ⁢ 
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           α 
                                           i 
                                         
                                       
                                       - 
                                       
                                         β 
                                         i 
                                       
                                     
                                     ) 
                                   
                                   / 
                                   2 
                                 
                               
                             
                             ; 
                           
                         
                       
                       
                         
                           
                             
                               
                                 1 
                                 2 
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     
                                       
                                         
                                           
                                             x 
                                             i 
                                           
                                           + 
                                           
                                             x 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                           - 
                                           
                                             
                                               1 
                                               2 
                                             
                                             ⁢ 
                                             
                                               ( 
                                               
                                                 
                                                   α 
                                                   i 
                                                 
                                                 + 
                                                 
                                                   β 
                                                   i 
                                                 
                                               
                                               ) 
                                             
                                           
                                         
                                         , 
                                       
                                     
                                   
                                   
                                     
                                       
                                         
                                           x 
                                           i 
                                         
                                         + 
                                         
                                           x 
                                           
                                             i 
                                             + 
                                             1 
                                           
                                         
                                         + 
                                         
                                           
                                             1 
                                             2 
                                           
                                           ⁢ 
                                           
                                             ( 
                                             
                                               
                                                 α 
                                                 i 
                                               
                                               + 
                                               
                                                 β 
                                                 i 
                                               
                                             
                                             ) 
                                           
                                         
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   x 
                                   i 
                                 
                               
                               + 
                               
                                 
                                   ( 
                                   
                                     
                                       3 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         α 
                                         i 
                                       
                                     
                                     - 
                                     
                                       β 
                                       i 
                                     
                                   
                                   ) 
                                 
                                 / 
                                 2 
                               
                             
                             &lt; 
                             
                               
                                 x 
                                 
                                   i 
                                   + 
                                   1 
                                 
                               
                               . 
                             
                           
                         
                       
                     
                   
                 
                 
                   
                     ( 
                     57 
                     ) 
                   
                 
               
             
           
         
       
     
     There are at least 8 cases; however, the two cases in the middle arise if and only if 3β i &gt;α i . 
     Logical Flow 
       FIG. 4  illustrates the logical flow for modifying a spline in accordance with one or more embodiments of the invention. 
     At step  402 , a spline is obtained. The spline is a set of connected points. As described above, the set of connected points may be points of vertical interest (PVIs), ground points, or any other points that may be connected to form a spline. More specifically, embodiments of the invention are directed towards a civil engineering spline (i.e., a spline used in the context of civil engineering) which may represent a road, a railway, a pipeline, a utility cable, a transport cable (e.g., cable cars, cabins, chair lifts, t-bars), etc. 
     At step  404 , a design constraint set is determined. The design constraint set may include various different types of constraints including an interpolation constraint, a slope constraint, and/or a curvature constraint. Each of these constraints is described below along with the specific method steps that are associated with each constraint during the projecting step of  406 . 
     At step  406 , the spline is projected onto the design constraint set which includes a modification of the spline (e.g., a modification/movement of the connected points in the spline). 
     At step  408 , the modified spline is projected onto the design constraint set iteratively until the spline satisfies all of the constraints in the design constraint set. 
     Some exemplary constraints in the design constraint set (e.g., interpolation, slope, and curvature) along with the actions associated with the projection of the spline onto the specific constraints are described herein. 
     Interpolation Constraint 
     An interpolation constraint defines a fixed elevation for one or more of the connected points in a spline. The projecting of the spline onto the design constraint set modifies the spline by changing a first elevation of a first connected point to match the fixed elevation. In an exemplary use case, at a certain station along a road, an engineer may have to fix an elevation at a certain point to allow for construction of an intersection with an existing road that crosses the new road within a given distance of that point. In embodiments of the invention, where the point in question is at a different elevation than the required one, the design of the road spline is modified by changing the elevation of that point so that it matches the required elevation. 
       FIG. 5  illustrates an exemplary vertical road profile in accordance with one or more embodiments of the invention. The dashed line  502  represents a vertical profile of the existing ground. The solid line  504  represents a spline that reflects the vertical profile of a road. With an interpolation constraint, one of the connected points  506  is fixed such that the road  504  must pass through that point  506  to intersect with an existing road (profile not shown). Thus, in embodiments of the invention, the spline may represent a vertical road profile  504 , where the connected point  506  having the fixed elevation defines an intersection point for an intersection between the vertical road profile  504  and an existing civil engineering infrastructure feature. Further, such an intersection is within a threshold distance of the existing civil engineering infrastructure feature. The existing civil engineering infrastructure feature may include a variety of features including another road, a lake, a cable, a railway, a feature that can be represented by a linear spline, etc. 
     Mathematically, the interpolation constraint may be represented using the following equation: 
               x   i     =     {             y   i     ,               if   ⁢           ⁢   i     ∈   I     ;                 x   i     ,           otherwise   .                   
for n connected spline points  506 , where x i  is a current elevation of the connected point i, for i=1, . . . , n, I is an index set referencing the connected points  506  that require a fixed elevation, and y i  is the required fixed elevation for the connected point i.
 
     Slope Constraint 
     A slope constraint defines a bound on a slope between two of the connected points. As an example, a bound may be a minimum required slope, an upper bound on the slope, and or a lower bound on the slope. When projecting the spline onto the design constraint set, the spline is modified by changing elevations of the two connected points to obtain a solution that satisfies the slope constraint. 
     In an exemplary road profile scenario, at a certain given PVI along the road, the engineer may have to respect a constraint on the slope to the next PVI. If the slope constraint is violated, then the two elevations are adjusted to obtain the nearest feasible solution satisfying the slope constraint by executing a projection operation. If no constraints are violated or considered, an engineer may adjust the two elevations to obtain another feasible solution that has the least change in elevation by executing a projection operation. 
       FIGS. 6A-6C  illustrate different slope bounds that may be utilized as constraints in accordance with one or more embodiments of the invention. In FIG.  6 A, the spline  602  has a defined slope. However, the slope of spline  602  exceeds the maximum slope (i.e., it is too steep). Accordingly, during the projection phase (i.e., step  406  of  FIG. 4 ), the elevations of both connected points are modified so that the spline complies with the maximum slope constraint thereby resulting in spline  604 . As an example, a maximum slope constraint may ensure that a road does not have an excessive grade (to accommodate certain vehicles). 
     In  FIG. 6B , spline  606  has no slope at all (i.e., it is flat). A slope constraint may require a minimum slope such that the elevations of the connected points defining spline  606  are modified resulting in spline  608 . A minimum slope may be required for drainage purposes such as on a road in Florida, a driveway, a man-made aqueduct, a pipeline, etc. Thus, the spline may represent a vertical road profile of a road and the bound on the slope is defined based on safety requirements for breaking, or traffic flow requirements for given design speeds, drainage requirements on a surface of the road, or flow requirements of waste water or drainage pipelines associated with the road. 
     In  FIG. 6C , spline  610  has a slope value that is negative, wherein the value of the slope exceeds the maximum. Accordingly, the elevations of the connected points are modified resulting in spline  612 . 
     In  FIGS. 6A-6C , different slope constraints are illustrated, including a minimum slope constraint ( FIG. 6A ), an upper bound slope constraint ( FIG. 6B ), and a lower bound slope constraint ( FIG. 6C ). 
     Of note that with all slope constraints, the solution is selected by selecting a solution associated with a minimum distance, in a metric space, from the connected points to a solution set of connected points that satisfy the slope constraint. In other words, given a solution set of all connected points that comply with the slope constraint, the connected points that are selected from that solution set are those points having elevations that provide a minimum distance in metric space. As used herein, metric space refers to the mathematical concept of a set where a notion of distance (called a metric) between elements of the set is defined. To compute such a minimum distance, a distance function may be used that includes, but is not limited to, the Euclidean distance, rectilinear distance, Chebyshev distance, or any other metric. Thus, the distances between the connected points to points in the solution set may be computed are compared, with the minimum distance selected as the solution. 
     Mathematically, as described above, for n connected points in the spline, let S i  be the solution set of connected points that satisfy the slope constraints between two connected points i and i+1. A projection P Si  that projects elevations x i  and x i+1  to the set S i  is defined as: 
               P     S   i       ⁢     :     ⁢           ⁢   x   ⁢     {               1   2     ⁢     (         x   i     +     x     i   +   1       +     α   i       ,       x   i     +     x     i   +   1       -     α   i         )       ,                 if   ⁢           ⁢     x   i       -     x     i   +   1         &gt;     α   i       ;                 (       x   i     ,     x     i   +   1         )     ,               if   ⁢           ⁢            x     i   +   1       -     x   i              ≤     α   i       ;                   1   2     ⁢     (         x   i     +     x     i   +   1       -     α   i       ,       x   i     +     x     i   +   1       +     α   i         )       ,               if   ⁢           ⁢     x     i   +   1         -     x   i       &gt;       α   i     .                     
wherein, α i  is a vertical bound on an elevation difference between the two connected points that will satisfy the bound for the slope constraint.
 
     In addition, in order to parallelize the execution of the projection, the set of slopes in the spline may be divided into two subsets. For the first subset, all of the slopes that start at even connected points/PVIs are picked, and for the second subset all of the slopes that start at odd connected points/PVIs are picked. This way, every connected point/PVI in a subset is changed only once in the projection. In other words, the projecting of the spline onto the design constraint set includes dividing the set of connected points into a first subset and a second subset, wherein the first subset contains all connected points that, starting with a first connected point, are spaced two points apart, and the second subset contains all connected points that, starting with a second connected point are spaced two points apart. Thereafter, all of the connected points in the first subset of connected points are projected onto the design constraint set in parallel. Similarly, all of the connected points in the second subset of connected points are projected onto the design constraint set in parallel. 
     As an alternative to the connected points reflecting a road spline, embodiments of the invention may provide that the connected points are existing ground points. When using existing ground points, a reference solution for the spline is obtained/acquired. The elevations of the connected points in the spline are modified with a projection-like operator that, if applied iteratively on the connected points, positions the connected points closer, using a distance measure in metric space, to the reference solution with each iteration. Stated mathematically, for n connected points in the spline, let x i  be the elevation of a connected point i in the spline, and z i  be the elevation for a connected point i in the reference solution for the spline. A projection-like operator that positions the connected points closer, using a Manhattan distance in Euclidean space, is defined as: 
     
       
         
           
             
               x 
               i 
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           x 
                           i 
                         
                         + 
                         
                           ɛ 
                           ⁢ 
                           
                             
                               
                                 z 
                                 i 
                               
                               - 
                               
                                 x 
                                 i 
                               
                             
                             
                                
                               
                                 
                                   z 
                                   i 
                                 
                                 - 
                                 
                                   x 
                                   i 
                                 
                               
                                
                             
                           
                         
                       
                       , 
                     
                   
                   
                     
                       
                         
                           if 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                              
                             
                               
                                 z 
                                 i 
                               
                               - 
                               
                                 x 
                                 i 
                               
                             
                              
                           
                         
                         &gt; 
                         ɛ 
                       
                       ⁢ 
                       
                           
                       
                     
                   
                 
                 
                   
                     
                       
                         z 
                         i 
                       
                       , 
                     
                   
                   
                     otherwise 
                   
                 
               
             
           
         
       
     
     wherein, ∈ is a tolerance value. 
     In an exemplary use case, an engineer may require a road profile that follows the ground profile as close as possible. The methods described herein may not guarantee that, as they aim for feasibility of the constraints only. Since iterative projection methods work also with other, projection-like operators, one can add a so-called “prox-operator” to approximate the existing ground profile. Given a reference solution, which in the infrastructure case is an existing ground profile, a prox-operator to approximate the ground profile as good as possible will move the connected spline points closer to the reference solution. If applied iteratively, it will move them closer in each iteration. However, used in an iterative method (e.g., as in step  408  of  FIG. 4 ) with the other projections, the prox-operator may not move the connected spline points exactly to the reference solution, as the reference solution could violate the design constraints, and the projections (e.g., onto the design constraint set described herein) will prevent convergence to the reference solution. 
     Curvature Constraint 
     The curvature constraint specifies a maximum slope difference of a first slope and a second slope (between three connected points—referred to as a first connected point, a second connected point, and a third connected point). When projecting the spline onto the design constraint set, the projecting modifies the spline by changing a first elevation of the first connected point, a second elevation of the second connected point, and a third elevation of the third connected point to obtain a solution satisfying the curvature constraint. 
     In an exemplary road profile scenario, at a certain given PVI along the road, an engineer may have to respect constraints on the differences of the slopes to the previous and next PVI. In embodiments of the invention, if that constraint is violated, then the three elevations are adjusted to obtain the nearest feasible solution by executing a projection operation. If no constraints are violated or considered, the engineer may adjust the three elevations to obtain another feasible solution that has the least change in slopes by executing a projection operation. 
       FIG. 7  illustrates a slope constraint in accordance with one or more embodiments of the invention. The three connected points have two segments  702  and  704 . A slope constraint may provide that the difference between the slopes of the two segments  702  and  704  cannot exceed a certain bound/threshold. In other words, the change in slope may be too abrupt. Accordingly, the elevations of the three points may be changed thereby resulting in modified spline having the two segments  706  and  708  that comply with the specified bounds. 
     In an exemplary use case, the spline represents a vertical road profile of a road and the maximum slope difference defines a maximum difference in road grades between two connecting sections (e.g., sections  702  and  704 ) of the road. 
     Similar to the slope constraint, the solution may be selected by selecting a solution associated with a minimum distance in a metric space, from the connected points to a solution set of connected points that satisfy the curvature constraint. 
     Mathematically, for n connected points in the spline, let C be a solution set of the connected points that satisfy the curvature constraints between three connected points i, i+1, and i+2. In addition, let τ i :=t i+1 −t i , τ i+1 :=t i+2 −t i+1  and u i  be a vector of length n with entries u i :=[0, . . . , 0, τ i+1 , −τ i −τ i+1 , τ i , 0, . . . , 0]. A projection P Ci  that projects elevations x i , x i+1  and x i+2  to the set C is defined as: 
                 P     C   i       ⁢     :     ⁢           ⁢   x     ↦     {             x   +             δ   i     ⁢     τ   i     ⁢     τ     i   +   1         -     〈       u   i     ,   x     〉                u   i          2       ⁢     u   i         ,               if   ⁢           ⁢     〈       u   i     ,   x     〉       &lt;       δ   i     ⁢     τ   i     ⁢     τ     i   +   1           ;               x   ,               if   ⁢           ⁢     δ   i     ⁢     τ   i     ⁢     τ     i   +   1         ≤     〈       u   i     ,   x     〉     ≤       γ   i     ⁢     τ   i     ⁢     τ     i   +   1           ;                 x   +             γ   i     ⁢     τ   i     ⁢     τ     i   +   1         -     〈       u   i     ,   x     〉                u   i          2       ⁢     u   i         ,             if   ⁢           ⁢     γ   i     ⁢     τ   i     ⁢     τ     i   +   1         &lt;       〈       u   i     ,   x     〉     .                     
wherein, &lt;u,x&gt; is an inner product between u and x, ∥u∥ is a norm of a vector u, and δ and γ are bounds on a slope change between the first connected point, the second connected point, and the third connected point.
 
     In addition, to parallelize the execution of the projection, the set of slopes may be divided into three subsets/groups: a first group contains all connected points that, starting with a first connected point, are spaced three points apart, and a second group contains all connected points that, starting with a second connected point, are spaced three points apart, and a third group contains all connected points that, starting with a third connected point, are spaced three points apart. Thereafter, all of the connected points in the first group of connected points may be projected onto the design constraint set in parallel. Similarly, all of the connected points in the second group of connected points may be projected onto the design constraint set in parallel, and all of the connected points in the third group of connected points may be projected onto the design constraint set in parallel. 
     Multiple Design Constraints 
     The logical flow described herein may also be followed when the design constraint set contains two or more constraints (e.g., the interpolation constraint, slope constraint, and curvature constraint). With such a constraint set, projections may be applied in a variety of manners iteratively until the solution set converges on a result that satisfies/complies with all of the constraints. 
     In other words, in addition to the interpolation constraint described above, the design constraint set may include a slope constraint that specifies a bound on a first slope between two of the connected points. If the design constraint set includes a slope constraint, the projecting step would also include the modification of the spline by changing elevations of the two connected points to obtain a solution satisfying the slope constraint. Further, the design constraint set may include a curvature constraint that specifies a maximum slope difference of a second slope (between a second connected point and a third connected point) and a third slope (between the third connected point and a fourth connected point). If the design constraint set includes the curvature constraint, the projection step would also include modifying the spline by changing a second elevation of the second connected point, a third elevation of the third connected point, and a fourth elevation of the fourth connected point to obtain a solution satisfying the curvature constraint. 
     To apply all different constraints, cyclical projection methods, parallel projection methods, or any other type of projection methods may be utilized. For example, in an exemplary use case with an initial civil engineering spline that represents a road, a railway, a pipeline, a utility cable, or a transport cable (e.g. cable cars, cabins, chair lifts, t-bars), embodiments of the invention may apply first the projection onto the interpolation constraint to satisfy all the fixed PVI requirements. With the newly obtained spline, embodiments of the invention may then apply the projection for the slope constraints (i.e., to satisfy all of the slope constraints). As described above, such a projection may first be performed on the even group of slopes, and then on the odd group of slopes. 
     The projections onto the slope constraints may invalidate the previous fixed PVI requirements (i.e., the interpolation constraint). Embodiments of the invention may then apply the curvature projections (e.g., first for groups of PVIs that start at the first position, following by the groups described above—e.g., a group starting with the second point and spaced 3 PVIs apart). However, such an application may invalidate the slope constraints again. Embodiments of the invention may then start with the fixed PVI constraint (i.e., the interpolation constraint) again and repeats the whole process iteratively. A general method to call projections in such a sequence is called a cyclic projection method and is known to converge to a solution that will satisfy all the constraints within a small tolerance. Embodiments of the invention make use of this cyclic projection method to find a feasible spline for a road, a railway, a pipeline, a utility cable, or a transport cable. 
     CONCLUSION 
     This concludes the description of the preferred embodiment of the invention. The following describes some alternative embodiments for accomplishing the present invention. For example, any type of computer, such as a mainframe, minicomputer, or personal computer, or computer configuration, such as a timesharing mainframe, local area network, or standalone personal computer, could be used with the present invention. 
     While embodiments of the invention may be utilized in road design optimization (or as a feature for CAD desktop software for civil engineering), it is not limited to road profiles. In computer graphics and mathematics, a spline is a curve that is made up of piecewise polynomial functions. It is widely used to approximate complex shapes with a curve. Embodiments of the invention can be used on any given linear spline that needs to be adapted to the constraints described herein. In CAD, examples include designs for pipelines (e.g., pipe layouts in water networks), utility cables, transport cables (e.g., cable cars, cabins, chair lifts, t-bars, etc.), fuel lines in automotive designs such as airplanes and cars, duct networks for heating systems, railways, etc. 
     The foregoing description of the preferred embodiment of the invention has been presented for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed. Many modifications and variations are possible in light of the above teaching. It is intended that the scope of the invention be limited not by this detailed description, but rather by the claims appended hereto. 
     REFERENCES 
     
         
         [1] American Association of State Highway and Transportation Officials,  A Policy on Geometric Design of Highways and Streets , sixth edition, Washington, D.C., 2011. 
         [2] H. H. Bauschke and P. L. Combettes,  Convex Analysis and Monotone Operator Theory in Hilbert Spaces , Springer, 2011. 
         [3] R. Bellman, On the approximation of curves by line segments using dynamic programming,  Comm. ACM  4(6) (1961), 284. 
         [4] G. T. Herman and W. Chen, A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy,  Linear Algebra Appl.  428 (2008), 1207-1217. 
         [5] V. R. Koch, Road Design Optimization, U.S. patent application Ser. No. 13/626,451, filed on Sep. 25, 2012.