Indexing (x 4 OR y 5)

I am searching for an index to make the following quick:

CREATE TABLE mytable (
    t1 INT NOT NULL, 
    t2 INT NOT NULL, 
    latest_creation_date INT NOT NULL, 
    data_category_id CHAR(36) NOT NULL, 
    value VARCHAR(255) NOT NULL,  
    PRIMARY KEY(latest_creation_date, t1, t2, data_category_id))

The query is a delete and reads:

delete 
from mytable 
where 
    latest_creation_date = 0 
    and Not (
           (t1 = 5 and t2 = 10)
        or (t1 = 15 and t2 = 20)
        or (t1 = 215 and t2 = 320)
        or (t1 = 315 and t2 = 420)
        ...
        or (t1 = 415 and t2 = 520)
        or (t1 = 515 and t2 = 620));

so it deletes all rows that do not match a few hundred criteria on t1 and t2.

explain gives a sequential scan and rearranges the query:

Delete on mytable  (cost=0.00..2517652.30 rows=38182950 width=6)
   ->  Seq Scan on mytable  (cost=0.00..2517652.30 rows=38182950 width=6)
         Filter: ((latest_creation_date = 0) AND ((t1 <> 5) OR (t2 <> 10)) AND ((t1 <> 15) OR (t2 <> 20)) AND ((t1 <> 215) OR (t2 <> 320)) AND ((t1 <> 315) OR (t2 <> 420)) AND ((t1 <> 415) OR (t2 <> 520)) AND ((t1 <> 515) OR (t2 <> 620)))

Can I create an index that will avoid that full scan?

Thanks in advance!

Answer

Although it should be the same plan, do either of these result in an improved plan?

delete from mytable 
where latest_creation_date = 0 and
      (t1, t2) not in ((5, 10), (15, 20), . . . );

Or:

delete from mytable 
where latest_creation_date = 0 and
      (t1, t2) not in (select v.*
                       from (values (5, 10), (15, 20), . . .) v(t1, t2)
                      );