TY - GEN
T1 - Preprocessing imprecise points and splitting triangulations
AU - Van Kreveld, Marc
AU - Löffler, Maarten
AU - Mitchell, Joseph S.B.
PY - 2008
Y1 - 2008
N2 - Given a triangulation of a set of n points in the plane, each colored red or blue, we show how to compute a triangulation of just the blue points in time O(n). We apply this result to show that one can preprocess a set of disjoint regions (representing "imprecise points") in the plane having total complexity n in O(n logn) time so that if one point per region is specified with precise coordinates, a triangulation of the n points can be computed in O(n) time.
AB - Given a triangulation of a set of n points in the plane, each colored red or blue, we show how to compute a triangulation of just the blue points in time O(n). We apply this result to show that one can preprocess a set of disjoint regions (representing "imprecise points") in the plane having total complexity n in O(n logn) time so that if one point per region is specified with precise coordinates, a triangulation of the n points can be computed in O(n) time.
UR - https://www.scopus.com/pages/publications/58549104964
U2 - 10.1007/978-3-540-92182-0_49
DO - 10.1007/978-3-540-92182-0_49
M3 - Conference contribution
AN - SCOPUS:58549104964
SN - 3540921818
SN - 9783540921813
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 544
EP - 555
BT - Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings
T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008
Y2 - 15 December 2008 through 17 December 2008
ER -