Free-Form Surface Partition in 3-D

We study the problem of partitioning a spherical representation

S

of a free-form surface

F

in 3-D, which is to partition a 3-D sphere

S

into two hemispheres such that a representative normal vector for each hemisphere optimizes a given global objective function. This problem arises in important practical applications, particularly surface machining in manufacturing. We model the spherical surface partition problem as processing multiple off-line sequences of insertions/deletions of convex polygons alternated with certain point queries on the common intersection of the polygons. Our algorithm combines nontrivial data structures, geometric observations, and algorithmic techniques. It takes

$O(\min\{m^2n \log \log m + \frac{m^3 \log^2(mn) \log^2(\log m)}{\log^3 m}, m^3\log^2n+mn\})$

time, where

m

is the number of polygons, of size

O

(

n

) each, in one off-line sequence (generally,

m

 ≤ 

n

). This is a significant improvement over the previous best-known

O

(

m

2

n

2

) time algorithm. As a by-product, our algorithm can process

O

(

n

) insertions/deletions of convex polygons (of size

O

(

n

) each) and queries on their common intersections in

O

(

n

2

loglog

n

) time, improving over the “standard”

O

(

n

2

log

n

) time solution for off-line maintenance of

O

(

n

2

) insertions/deletions of points and queries. Our techniques may be useful in solving other problems.