| Geometric constraints are at the heart of CAD/CAM applications and also arise in many geometric modeling contexts such as virtual reality, robotics, molecular modeling, teaching geometry, etc.; Informally, a geometric constraint problem consists of a finite set of geometric objects and a finite set of constraints between them. The geometric objects are drawn from a fixed set of types such as points, lines, circles and conics in the plane, or points, lines, planes, cylinders and spheres in 3 dimensions. The constraints are spatial and include logical constraints such as incidence, tangency, perpendicularity and metric constraints such as distance, angle, radius. The spatial constraints can usually be written as algebraic equations whose variables are the coordinates of the participating geometric objects. A solution of a geometric constraint problem is a real zero of the corresponding algebraic system.; Currently there is a lack of effective spatial variational constraint solvers and assembly constraint solvers that scale to large problem sizes and can be used interactively by the designer as conceptual tools throughout the design process.; The requirement is a constraint solver that uses geometric domain knowledge to develop a plan for decomposing the constraint system into small subsystems, whose solutions can be recombined by solving other small subsystems. The primary aim of this decomposition plan is to restrict the use of direct algebraic/numeric solvers to subsystems that are as small as possible. Hence the optimal or most efficient decomposition plan would minimize the size of the largest such subsystem. Any geometric constraint solver should first solve the problem of efficiently finding a close-to-optimal decomposition-recombination (DR) plan, because that dictates the usability of the solver.; In this thesis we state this problem of finding a close-to-optimal solution as a problem that deals with weighted graphs and also identify several important subproblems. One class of such subproblem involves finding dense subgraphs---graphs such that sum of weights of its edges is greater than sum of weights of its vertices. Dense graphs that present interest for finding a DR-plan are (a) minimum (smallest possible dense graphs), (b) minimal (not containing any other dense subgraphs), (c) maximum (largest dense ones), (d) maximal (not contained in any other dense subgraph).; This thesis presents polynomial time algorithms for problems (b), (c) and (d). Problem (a) is shown to be NP-complete, and various approximation algorithms are suggested, as well as explicit solutions for special cases that arise from CAD/CAM applications. |
